A similar to 0–1 Knapsack DP problem
2218. Maximum Value of K Coins From Piles
1 min readApr 15, 2023
This problem is very similar to the 0–1 Knapsack problem.
0–1 Knapsack
For each item,
we can pick up 0 or 1
This one
Define each pile,
we can pick up 0, 1, ..., m where m is total number of item in this pile.
Code
int INF = 0x3f3f3f3f;
class Solution {
public:
int n;
int _maxValueOfCoins(vector<vector<int>>& piles, int i, int k, vector<vector<int>>&memo){
// Define i as the piles[i],
// we can pick up 0, 1, ..., m where m is total number of item in this pile.
if (k == 0) return 0;
if (k < 0) return -INF;
if (memo[i][k] != -1)return memo[i][k];
if (i>=n)return memo[i][k] = -INF;
int tot = 0;
int ret = _maxValueOfCoins(piles, i + 1, k, memo) ;
for (int j = 0; j < piles[i].size(); ++j){
tot += piles[i][j];
ret = max(ret, tot + _maxValueOfCoins(piles, i + 1, k - (j + 1), memo) );
}
return memo[i][k] = ret;
}
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
this -> n = piles.size();
vector<vector<int>>memo(n + 1, vector<int>(k + 1, -1));
return _maxValueOfCoins(piles, 0, k, memo);
}
};
For the meaning of 0x3f3f3f3f see the following article.