Detailed explanation of knapsack problem

Focus on mastering 01 Backpack and full backpack

01 Backpack details ：
https://blog.csdn.net/u013445530/article/details/40210587
dp[i][j]=max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
explain ：1） Put in the i An object , be dp[i][j]=dp[i-1][j - w[i]] + v[i];
2) Don't put it in the second i An object :dp[i][j]=dp[i-1][j];

Two dimensional array

for(int i = 1; i <= n; i++)
    {
    
        for(int j = 0; j <= W; j++)
        {
    
            if(j < w[i])    dp[i][j]  = dp[i-1][j];
            else dp[i][j] =  max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
        }
    }

To a one-dimensional array ,dp[i][j] As dp[j].
dp[i][j] By dp[i-1][j] and dp[i-1][j-w[i]] Derived from , be dp[j] from dp[j] and dp[j - w[i]] Derived from .

for(int i = 1; i <= n; i++)
    {
    
     for(int j = W; j >= w[i]; j--)
        	dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }

The following figure helps to understand why it is necessary to reverse the order when changing to one dimension ：
Traverse horizontally , To make sure dp[j - w[i]] What is kept is dp[i-1][j - w[i]] Value , First i=1 when , Traverse from right to left

Here is traversal in reverse order , If you don't traverse back in reverse order, it will cause an item to be selected repeatedly .
Why repeat selection ？ The maximum value of the back is from the value of the front , The first value is selected i Item , The following capacity can still be selected i Item , Lead to i Items selected repeatedly .
``
However, the complete knapsack problem happens to be an item n Pieces of , It just needs to be selected repeatedly , So the ergodic order is positive ergodic , as follows ：

for(int i = 1; i <= n; i++)
    {
    
     for(int j = w[i]; j <= W; j++)
        	dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }