44. 0-1 Knapsack

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

Solution: (Recursion)

int findMaxRecusive(vector<int> &items, vector<int> &weight, int c, int pos, int maxItems)
{

    if (items.size() == pos)
    {
        return maxItems;
    }

    int res = 0;

    if (weight[pos] <= c)
    {
        int inc = findMaxRecusive(items, weight, c - weight[pos], pos + 1, maxItems + items[pos]);
        int exc = findMaxRecusive(items, weight, c, pos + 1, maxItems);
        res = max(inc, exc);
    }
    else
    {
        int exc = findMaxRecusive(items, weight, c, pos + 1, maxItems);
        res = exc;
    }

    return res;
}

Solution: (DP)

int Solution::solve(vector<int> &A, vector<int> &B, int C)
{
    int n = A.size();
    vector<vector<int>> dp(n + 1, vector<int>(C + 1, 0));

    for (int i = 1; i <= n; i++)
    {
        int w = B[i - 1];
        int v = A[i - 1];
        for (int j = 1; j <= C; j++)
        {
            if (w <= j)
            {
                int inc = v + dp[i - 1][j - w];
                int exc = dp[i - 1][j];
                dp[i][j] = max(inc, exc);
            }
            else
            {
                int exc = dp[i - 1][j];
                dp[i][j] = exc;
            }
        }
    }

    return dp[n][C];
}