闫式dp分析法

1 . f数组的后半部分，f[j~m]处于'第i个阶段'，也就是已经考虑过放入第i个物品的情况.
2 . 前半部分 f[0~j-1]处于'第i-1个阶段',也就是还没有第i个物品更新
    接下来j不断减小，意味着我们总是用'第i-1个阶段'的状态向'第i个阶段'的状态进行转移,符合线性DP的原则，进而保证了第i个物品只会被放入背包一次



如果采用正序的话 : 
然而，如果使用正序循环，假设f[j]被f[j-vi]+wi更新，接下来j增大到j+vi时，f[j+vi]又可能被f[j]+wi更新。此时,两个都处于'第i个阶段'的状态之间发生了转移，违背了线性dp的原则，相当于第i个物品被使用了两次
    f[j-vi] = f[j-2vi]+wi;//不选第i个
    f[j]=f[j-vi]+wi=f[j-2vi]+2wi;//选第i个

    f[j] = f[j-vi]+wi;
    f[j+vi]=f[j]+wi;
    f[j]和f[j-vi]+wi比更新了一次 ， 然后j增大到j+vi时 f[j]再次使用了一次


#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int f[N]; //状态转移方程
int v[N] , w[N];
int n ,m; // n 代表物品个数，m代表背包体积

int main() {
    cin >> n >> m;

    for (int i = 1 ; i <= n ; i ++ ) cin >> w[i] >> v[i];
    for (int i = 1 ; i <= n ;  i++ ) { //i从1开始因为下面会用到i - 1 ，避免数组下标越界
        for (int j = m ; j >= w[i] ; j -- ) {
           f[j] = max(f[j] , f[j - w[i]] + v[i]);
        }
    }
    cout << f[m] << endl;
}
    关于滚动数组优化为什么要逆序的原因 : 
for (int i = 1 ; i <= n ;  i++ ) { //i从1开始因为下面会用到i - 1 ，避免数组下标越界
        for (int j = m ; j >= w[i] ; j -- ) {
           f[j] = max(f[j] , f[j - w[i]] + v[i]);
        }
    }