DSA
Knapsack with Duplicate Items
Memoized Version approach. Optimal — Time O(n x W), Space O(n).
Practice Link
Given a set of items, each with a weight and a value, represented by the array wt and val respectively. Also, a knapsack with a weight limit capacity. The task is to fill the knapsack in such a way that we can get the maximum profit. Return the maximum profit. Note: Each item can be taken any number of times.
Memoized Version#
Unlike 0-1 knapsack, items can be reused, so the "take" branch stays at the same item index n instead of moving to n-1. The base case uses the lightest item (index 0) greedily: take as many copies as fit (W / wt[0]). Each (n, W) state is unique and cached in memo[n][W], giving O(n × W) total evaluations. The recursion stack adds O(n) overhead.
class Solution {
public:
int solve(vector<int>& val, vector<int>& wt, int n, int W,vector<vector<int>> &memo )
{
if(n==0)
return (W/wt[0]) * val[0];
if(memo[n][W] != -1)
return memo[n][W];
int take = INT_MIN, not_take=INT_MIN;
if(wt[n] > W)
not_take = solve(val, wt, n-1, W, memo);
else
take = val[n] + solve(val, wt, n, W-val[n], memo);
return memo[n][W] = max(take, not_take);
}
int knapSack(vector<int>& val, vector<int>& wt, int capacity) {
int n = val.size();
vector<vector<int>> memo(n, vector<int> (capacity+1, -1));
return solve(val, wt, n-1, capacity, memo);
}
};
Time Complexity: O(n x W)
Space Complexity: O(n x W) + O(n) -> recursion stack