# A similar to 0–1 Knapsack DP problem

## 2218. Maximum Value of K Coins From Piles

--

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.

--

--