Knapsack with Duplicate Items

Given a set of N items, each with a weight and a value, represented by the array w[] and val[] respectively. Also, a knapsack with weight limit W.
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.

• Time : O(nw)
• Space : O(w)

class Solution {
public:
    int knapSack(int N, int W, int val[], int wt[]) {
        vector<int> dp(W + 1, - 1);
        int res = 0;
        dp[0] = 0;
        for(int i = 0; i < N; i++) {
            for(int j = wt[i]; j <= W; j++) {
                if(dp[j-wt[i]] == -1) continue;
                dp[j] = max(dp[j], dp[j-wt[i]] + val[i]);
                res = max(res, dp[j]);
            }
        }
        return res;
    }
};