对于放入第2个物品,容量为3的枚举，dp[3]= 6, 6= dp[3-2]+6
对于放入第2个物品,容量为4的枚举，dp[4]= 12, 12= dp[4-2]+6
在第4次枚举的时候发现问题,
原因在于dp[4]=dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
dp[4]=dp[2]+6 = 6+6
然鹅,dp[2]已经更新过,通过装入物品2,
此时dp[2]的值是容量为2的时候的最大值,
在这个过程里, 第2个背包被使用了两次,
重复枚举就是利用先更新容量小的背包实现的
而dp[5]则是直接继承了dp[4]
每次都利用之前的最大值,并且每个背包都放进去试一试, 可以继承已经更新过的–前驱背包的–“最大价值”, 也就可以重复无限次,
这样枚举出来的结果是完全背包的最大价值

逆序
不存在: 容量小的背包在容量大的背包被更新之前就更新过
结论: 顺序枚举是可取无限次物品的结果, 逆序枚举是每种物品只取一次的结果

01背包

#include<iostream>
using namespace std;

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

完全背包

#include<iostream>
using namespace std;

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

多重背包1

#include<iostream>
using namespace std;

const int N = 1010;

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

int main(){
    int v,w,s;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){

        cin >> v >> w>>s;
        for(int i=1;i<=s;i++){
        for(int j = m; j >= v; j -- ){
                dp[j] = max(dp[j], dp[j - v] + w);
            }
        }
    }
    cout << dp[m] << endl;
}