help on 0-1 knapsack

help
, ,
1

I just came across this code snippet of 0-1 knapsack

int knapsack_01(int *val, int *wt, int n, int W)
{
    int dp[W+1];
    fill(dp, dp + W +1, 0);

    for(int i = 0; i < n; i++)
        for(int j = W; j >= 0; j--)  //why this loop needs to iterate in reverse order?
            if(wt[i] <= j && dp[j] < dp[j - wt[i]] + val[i])
                    dp[j] = dp[j - wt[i] + val[i];

    return dp[W];
}

and could not understand why the second loop involving ‘j’ has to run in reverse order to get the answer correct?

I get WA for 0-1 knapsack if I iterate j from 0 to W

NOTE: both the arrays ‘val’ and ‘wt’ are 0-based indexed.

someone please help…

2

Normally, when solving the knapsack problem, you would create a 2D dp array, where dp[i][w] is the maximum value you can obtain if your weight limit is w and you can only use the first i items. The recursion would be something like

dp[i][w] = max(dp[i-1][w],dp[i-1][w-wt[i]]+val[i])

Note that the update equation for each cell depends only on the elements to the left of that cell in the previous row. This means that we we can reduce the memory requirements by keeping track of only the current row and the last row. However, we can do even better. Since the value of a cell only depends on the elements to the left, we can keep track of only the current row. So when we iterate over the second coordinate in a backwards fashion, we still keep the old values to the left of our cell from the previous row and our update equation would still be correct. When we iterate over the second coordinate in a forwards fashion, we would be overwriting these coordinates. So instead of using dp[i-1][w-wt[i]] for example, we would be using d[i][w-wt[i-]]. This is what causes the WA. Hope that helps.

1 Like
3

That was a great help. Thanks buddy :slight_smile:

4

I like you post, you’re properly assured that your shopping editorial will inspire humans and sure that is so proper! i am inspired by it. thanks for sharing. samishleather