【35. 多重背包】

多重背包

• 多重背包背包数量是有限个。
• 所有背包问题的状态表示都是一样的（只是状态计算有所区别）
• 在状态计算时，与完全背包集合划分是类似的

暴力解法：

#include 
#include 
using namespace std;

const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];


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 = 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]] + k * w[i]);
            }
        }
    }
    cout << f[n][m];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

优化（二进制优化）

疑惑1：为什么最后一项会是f[i-1,j-(S+1)v]+Sw??

在完全背包中,通过两个状态转移方程：

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w, .....)
f[i , j-v]= max(            f[i-1,j-v] ,   f[i-1,j-2v] + w, f[i-1,j-2v]+2w,.....)

通过上述比较，可以得到 f[ i ][ j ] = max(f[ i - 1 ][ j ],f[ i ][ j - v ] + w)。
1
2
3
4

再来看下多重背包:

f[i , j ] = max( f[i-1,j] ,f[i-1,j-v]+w ,f[i-1,j-2v]+2w ,..... f[i-1,j-Sv]+Sw, )
f[i , j-v]= max( f[i-1,j-v] ,f[i-1,j-2v]+w, ..... f[i-1,j-Sv]+(S-1)w, f[i-1,j-(S+1)v]+Sw )
1
2

怎么比完全背包方程比较就多出了一项?

• 其实，一般从实际含义出发来考虑即可，这里是在分析f[i,j-v]这个状态的表达式，首先这个状态的含义是 从前i个物品中选，且总体积不超过j-v的最大价值， 我们现在最多只能选s个物品，因此如果我们选s个第i个物品，那么体积上就要减去 s * v,价值上就要加上s * w，那更新到状态中去就是 f[i - 1, j - v - s * v] + s * w。

那为什么完全背包不会有最后一项？

• 完全背包由于对每种物品没有选择个数的限制，所以只要体积够用就可以一直选，没有最后一项。

疑惑2：为什么不能用像完全背包一样去优化？

• （如果根据总和 - 最后一个数 = 前面所有数的和），但是不能根据所有数的最大值 - 最后一个数，来获得前面所有数的最大值

疑惑3：二进制优化，它为什么正确，为什么合理，凭什么可以这样分？

我们首先确认三点：

（1）我们知道转化成01背包的基本思路就是：判断每件物品我是取了你好呢还是不取你好。

（2）我们知道任意一个实数可以由二进制数来表示，也就是2^0~2k其中一项或几项的和。

（3）这里多重背包问的就是每件物品取多少件可以获得最大价值。

分析：

• 如果直接遍历转化为01背包问题，是每次都拿一个来问，取了好还是不取好。那么根据数据范围，这样的时间复杂度是O(n^3),也就是1e+9，这样是毫无疑问是会TLE的。

• 假如10个取7个好，那么在实际的遍历过程中在第7个以后经过状态转移方程其实已经是选择“不取”好了。现在，用二进制思想将其分堆，分成k+1个分别有2 ^ k个的堆，然后拿这一堆一堆去问，我是取了好呢，还是不取好呢，经过dp选择之后，结果和拿一个一个来问的结果是完全一样的，因为dp选择的是最优结果，而根据第二点任意一个实数都可以用二进制来表示，如果最终选出来10个取7个是最优的在分堆的选择过程中分成了2 ^ 0=1,2 ^ 1=2,2^2=4,10 - 7 = 3 这四堆，然后去问四次，也就是拿去走dp状态转移方程，走的结果是第一堆1个，取了比不取好，第二堆2个，取了比不取好，第三堆四个，取了比不取好，第四堆8个，取了还不如不取，最后依旧是取了1+2+4=7个。

苹果例子

• 如果仍然不是很能理解的话，取这样一个例子:要求在一堆苹果选出n个苹果。我们传统的思维是一个一个地去选，选够n个苹果就停止。这样选择的次数就是n次

• 二进制优化思维就是：现在给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照1,2,4,8,16,.....512分到10个箱子里，那么由于任何一个数字x ∈[1,1024]
  都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10次 。

• 这样利用二进制优化，时间复杂度就从O(n ^ 3)降到O(n ^ 2logS),从4*10^9降到了2*10^7。

题目

代码

#include
using namespace std;

const int N = 25000, M = 2010;
//一共1000个物品，每个物品有2000个，那么最多分成log2000组，所以一共是1000 * log2000

int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积

int main()
{
    cin >> n >> m;
    int cnt = 0; //分组的组别
    for(int i = 1;i <= n;i ++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1; // 组别里面的个数
        while(k<=s)
        {
            cnt ++ ; //组别先增加
            v[cnt] = a * k ; //整体体积
            w[cnt] = b * k; // 整体价值
            s -= k; // s要减小
            k *= 2; // 组别里的个数增加
        }
        //剩余的一组
        if(s>0)
        {
            cnt ++ ;
            v[cnt] = a*s; 
            w[cnt] = b*s;
        }
    }

    n = cnt ; //枚举次数正式由个数变成组别数

    //01背包一维优化
    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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

对比

参考博客https://www.acwing.com/solution/content/20115/