整理记录一下各种背包问题的模型。
有些地方或者代码使用的是我之前的笔记，所以可能分析时是dp数组，代码中是f数组，但这影响很小。

01背包

dp[i][j] 表示从前i个物品中选，且体积不超过j的所有选法中所获价值最大的
状态转移：
选择第i个物品：dp[i][j] = dp[i-1][j-v[i]] + w[i]
不选第i个物品： dp[i][j] = dp[i-1][j]

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

01背包空间优化

我们发现状态转移时只用到了第i-1层的状态，所以我们可以使用滚动数组把第一维优化掉
注意两点：
1.为什么反向遍历？
正向遍历的话，这一层前面更新的值会覆盖掉上一层的值，导致后面的更新出错
2.为什么j不需要到走到1
如果j < v的话，那么dp[j] = max(0,dp[k]) = dp[k] ，dp[k] 没有得到更新，所以可以直接跳出循环

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

完全背包

与01背包不同的是，对于完全背包，每个物品可以拿任意个，所以状态表示可以和01背包一样，只不过在状态转移时我们需要枚举当前第i个物品拿几个，代码：

for(int i = 1; i<=n ;i++)
        for(int j = 0; j<=m ;j++)
            for(int k = 0; k*v[i]<=j ;k++)
                f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

完全背包优化

与01背包一样的思路，只不过由于物品是无限个，所以我们不用逆序，而是考虑用第i层中前面体积较小的背包来更新后面的状态，因为第i个物品在体积较小的背包里面可能已经拿了多个。
推导：
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2 * v]+2 * w , f[i-1,j-3 * v]+3 * w , ...)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2 * v] + w , f[i-1,j-2 * v]+2 * w , ...)
比较两式：
dp[i][j] = max(dp[i-1][j], dp[i,j-v]+w);(从这个式子也可以看出来我们应该使用第i层进行更新）
可以发现，正序：对应第i层。
逆序：对应第i-1层。

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

多重背包1

每件物品有多个，不是无限个(区别于完全背包),但数据量较小（0<N,V≤100）,思维和完全背包一样，最后一个循环枚举第i个物品选的个数就行了

for(int i = 1; i<=n; i++){
        for(int j = 0; j<=m; j++){
            for(int k = 0; k<=s[i] && k*v[i]<=j; k++){
                f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + w[i]*k);
            }
        }
    }

多重背包2

题意与多重背包1一样，数据范围(0<N≤1000,0<V≤2000)，所以不能使用上面的暴力做法，我们考虑使用二进制进行优化。
对于一个十进制的数k，我们能否用少量的数字表示0~ k的任意一个数字，答案是肯定的，例如，对于十进制数字13，我们可以利用二进制数拆分为1，2，4，6，这四个数就能表示1~13的任意一个数，这样枚举s个物品的复杂度由O(s) 降低到O(logs)。
证明一下： 对于数字k，我们找到最大的一个011..11(B)<k
k = 011..11 + (k-01111.111)
假设011..11对应的十进制数字是a，
我们将这个011..11拆分成 000..01, 000..10,..., 001..00, 010..00
那么这些二进制数很明显可以组成0_{a之间的所有数，再加上最后那个k-a，那么就可以表达0}k的所有数啦。
分完后，我们就可以按照01背包来做了，因为物品数目我们是可以通过枚举一一得到的。

for(int i = 1; i<=n; i++){
        int a,b,s;
        cin>>a>>b>>s;
        
        int t = 1;
        while(t<s){
            w[idx] = t*b;
            v[idx++] = t*a;
            s -= t;
            t<<=1;
        }
        w[idx] = s*b;
        v[idx++] = s*a;
    }
    
    n = idx; //组数
    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]);

分组背包

每组有若干个物品，但是同一物品只能选一个。
dp[i][j] 表示前i组里面选，体积不超过j的所有选法的最大价值
dp[i][j] = max(dp[i][j], dp[i-1][j-v[i][k]]+w[i][k]; //k表示第i组的第k个物品
思想和01背包类似，空间上也可以使用滚动数组进行优化。

for(int i = 1; i<=n; i++){
        for(int j = m; j>=0; j--)
            for(int k = 0; k<=s[i]; k++)
            if(j>=v[i][k])
                f[j] = max(f[j],f[j-v[i][k]] + w[i][k]);

背包模型