什么是多重背包问题？

有n种物品和一个容量是

m

$m$

的背包。第

i

$i$

种物品最多有

i

s_i

$s_{i}$

件，每件体积是

i

v_i

$v_{i}$

，价值是

i

w_i

$w_{i}$

。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大，输出最大价值。

dp问题的通用分析方法

在这里插入图片描述

先考虑用几维状态来表示，背包问题一般用两维表示。【经验】
状态计算是把每个状态一步一步算出来。
DP优化一般是指对动态规划的代码或计算方程做一个等价变形。一般是先将最基本的代码写出来再考虑去优化。
这里介绍的DP理解方式是从集合的角度去理解。这里以0-1背包为例子，

f(i, j)
对应一个集合，是只考虑前
i
个物品，且背包容量不超过
j
的所有选法构成的一个集合。

（一个选法是指从第1到第
i
个物品，经过的物品你要么选，你要么不选，这就构成一种选法）
f(i, j)
一定是集合的某种属性（这种属性一般可以是Max、Min、数量等等）

具体分析

在这里插入图片描述

公式推导类似完全背包过程，不熟悉的朋友可以参考我写的

完全背包问题

。

代码——朴素版

#include <iostream>
using namespace std;

const int N = 110;
int f[N][N], v[N], w[N], s[N];
int n, m;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int k = 0; k <= s[i] && k * v[i] <= j; k++){
                // k == 0时包含了f[i - 1][j]这种情况
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] +  k * w[i]);
                
            }
        }
        
    }
    cout << f[n][m];
    return 0;
}

时间复杂度为O(nms)，其中s为每个物品的最大数量，n为物品个数，m为背包最大容量。

那么复杂度过高有什么优化方法呢？

是否可以参照完全背包的做法去做优化呢？

在这里插入图片描述

如果按照类似完全背包问题去做，见上图中
f[i, j - v[i]]
多了一项
f[i - 1, j - (s + 1) * v] + s * w
，所以没办法直接按完全背包方法做，所以引入二进制优化其中一种做法（当然，还有一种采用单调队列优化的极致做法）。

二进制优化

优化思路

：如果第

i

$i$

件物品总数为s = 1023，那么它有0 ~ 1023种选法，利用二进制的性质，我们可以把物品打包成数量分别为1、2、4、8、…、512的不同种类的物品，通过拼凑的方式可以表示0 ~ 1023种选法，比如：100 = 64 + 32 + 4，那么这样处理后就可以用0-1背包问题模型解决了。

但是这里又有一个问题，如果s = 200，如果打包为1、2、4、8、…、128，表示的数字范围是0 ~ 255，但物品只有200，所以128不能取，取什么呢？取200 – (1 + 2 + … + 64) = 200 – 127 = 73，因为1、2、4、8、…、64可以表示0 ~ 127范围的数字，加上73就能表示73 ~ 200范围的数字，所以证明了最后补上一个73是能够表示73 ~ 200范围数字的，结合0 ~ 127和73 ~ 200，那么1、2、4、8、…、64、73是可以表示0~200内的数字的。

代码——二进制优化

#include <iostream>
using namespace std;

const int N = 11010, M = 2010;
int f[N][M], v[N], w[N];
int n, m;
int cnt = 0;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        int k = 1;
         // 优化思路：如果第i个物品总数s = 1023，那么它有0~1023种选法，
        // 利用二进制的性质，我们可以把物品打包成数量分别为1、2、4、8、...、512的不同种类的物品，
        // 通过拼凑的方式可以表示0~1023种选法，比如：100 = 64 + 32 + 4，
        // 那么这样处理后就可以用0-1背包问题模型解决了。
        
        // 这里又有一个问题，如果s = 200，如果打包为1、2、4、8、...、128，表示的数字范围是0~255，
        // 但物品只有200，所以128不能取，取什么呢？取200 - (1 + 2 + ... + 64) = 200 - 127 = 73，
        // 因为1、2、4、8、...、64可以表示0~127范围的数字，加上73就能表示73~200范围的数字，
        /// 所以证明了最后补上一个73是能够表示73~200范围数字的，结合0~127和73~200，
        // 那么1、2、4、8、...、64、73是可以表示0~200内的数字的。
        while(k <= z){
            cnt++;
            v[cnt] = k * x;
            w[cnt] = k * y;
            z -= k;
            k <<= 1;
        }
        // 处理剩余物品，将其打包为一个新的物品
        if(z){
            cnt++;
            v[cnt] = z * x;
            w[cnt] = z * y;
        }
    }
    n = cnt;// 更新物品真实数量
	
	// 0-1背包代码
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            f[i][j] = f[i - 1][j];
            if(v[i] <= j) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
        
    }
    cout << f[n][m];
    return 0;
}

代码——0-1背包代码优化

具体优化策略请看我写的

0-1背包详解

#include <iostream>
using namespace std;

const int N = 11010, M = 2010;
int f[M], v[N], w[N];
int n, m;
int cnt = 0;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        int k = 1;
        while(k <= z){
            cnt++;
            v[cnt] = k * x;
            w[cnt] = k * y;
            z -= k;
            k <<= 1;
        }
        if(z){
            cnt++;
            v[cnt] = z * x;
            w[cnt] = z * y;
        }
    }
    n = cnt; // 更新物品真实数量
    // 优化为一维
    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];
    return 0;
}

原文链接：https://blog.csdn.net/Sx_WWj/article/details/129388835