On the inverse order problem of 01 knapsack problem in one-dimensional state

I hope my explanation below will be helpful to you

Classic title

Topic link ：

2. 01 knapsack problem - AcWing Question bank

I like this algorithm platform very much , It is recommended that you can go to the above to learn algorithms

Title Description ：

2. 01 knapsack problem ​​​​​

Yes N Items and a capacity are V The backpack . Each item can only be used once .

The first i The volume of the item is vi, The value is wi.

Find out which items to pack in your backpack , The total volume of these items can not exceed the capacity of the backpack , And the total value is the greatest .
Output maximum value .

I won't specifically talk about the two-dimensional approach here , If you are not very clear about the two-dimensional approach , Then you can search on the Internet , The focus here is on why the cycle should be in reverse order

Two dimensional approach ：

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int f[N][N];
int w[N],v[N];
int n,m;

int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
    cin >> v[i] >> w[i];
    for(int i = 1;i <= n;i ++)
    for(int j = 0;j <= m;j ++){
        f[i][j] = f[i-1][j];
        if(j >= v[i])
        f[i][j] = max(f[i][j],f[i-1][j - v[i]] + w[i]);
    }
    cout << f[n][m];
    return 0;
}

One dimensional approach ：

#include<iostream>

using namespace std;

const int N = 1010;

int v[N],w[N];
int n,m;
int f[N];

int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
    cin >> v[i] >> w[i];
    
    for(int i = 1;i <= n;i ++)
    for(int j = m;j >= v[i];j --){
        f[j] = max(f[j],f[j - v[i]] + w[i]);
    }
    cout << f[m] << endl;
    return 0;
}

First of all, I want to state , commonly DP The optimization of is to make equivalent deformation of the code , For example, the two dimensions above become one dimension , It is completely equivalent in code , Just the order of the cycle is different , Why? ？

        In fact, the reason is not very difficult , First of all, let's look at this formula ：f[i][j] = max(f[i][j],f[i-1][j - v[i]] + w[i]); We can see very clearly f[i-1][j - v[i]] This variable is The first i - 1 Layer of , and f[i][j] It's No i Layer of , The so-called layer here is the first for The number of cycles in . It seems that the relationship between this and reverse order is not very big , good , Then come again , Let's first assume that the cycle is from small to large , In that case ,j Is increasing ,j - v[i] It's also incremental , j - v[i] Less than or equal to j , And because of j From small to big , So in the second for in ,j - v[i] It may have appeared  j 了 （ In fact, this situation is bound to happen , An example will be given later ）. Actually, it's good, such as , There are two numbers a,b( hypothesis b = a - 3),a from 3  Start to grow b from 0 Start to grow ,

a: 3 4 5 6 7 8 9 10....

b: 0 1 2 3 4 5 6 7....

Found it. , As the number increases ,b The number of will be a The number that has appeared before （ ad locum ,a It's just like j , b It's just like j - v[i],3 It's like v[i], Namely b It will be in this layer a The number that has appeared ）.

Well, in this case , j - v[i] Namely The first i On the floor , Then it is contradictory to the formula .

        Maybe you will think like this , Then why doesn't the above situation happen in reverse order ？ Here it is , When we reverse the order ,j It's from big to small ,j - v[i] From big to small ,j - v[i] Less than or equal to j, and j yes Decreasing , therefore j - v[i] Will be strictly smaller than before j 了 . Let's take the same a ,b(b = a - 3) For example

a: 10 9 8 7 6 5....

b:   7 6 5 4 3 2....

Found it. , hinder b Is strictly less than a The history of . in other words j - v[i] It's on the upper floor . Certificate completion ！

Because the author is still on the way , So if there are deficiencies , Please also correct in the comment area , thank you ！

I hope my explanation above is helpful to you , thank you ！