题目

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N ≤ 1000
0 < V ≤ 2000
0 < vi,wi,si ≤ 2000

提示

本题考查多重背包的二进制优化方法。

输入样例

1
2
3
4
5
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例

1
10

思路

朴素写法

和完全背包只相差一个 k 循环的循环条件：

1
2
3
4
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++)
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);

多重背包可以看成是 01 背包的一个扩展，所以可以按照 01 背包的方法压缩到一维

1
2
3
4
for(int i = 1; i <= n; i++)
    for(int j = m; j >= 0; j--)	// 需要逆序
        for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
            dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);

当然这样写肯定是 TLE，所以需要优化

优化

思路：把物品 i 共 s 件拆分为 t 个物品，每个物品 1 件，这样就能转换成 01 背包来做

那么怎么来拆分呢？

一件一件拆分，s 件分成 s 个物品？这样显然不行

那么怎么办呢？办法就是二进制拆分，举个例子吧：

s = 200
拆分：1, 2, 4, 8, 16, 32, 64，还剩下 73
由 1, 2, 4, 8, 16, 32, 64 可以组成 1~127 之间的任何一个数，再加上 73 就可以组成 1~200 之间的任意一个数

这样就能把多重背包某个物品有 s 次，转化为 logs 的物品的 01 背包问题

最终代码

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
#include<bits/stdc++.h>
using namespace std;

const int N = 11010;	// 1000 * log2000 = 1000 * 11 = 11000
int dp[N], v[N], w[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int idx = 0;
    for(int i = 0; i < n; i++) {	// 二进制拆分
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        for(int k = 1; k <= c; k *= 2) {
            v[++idx] = k * a;
            w[idx] = k * b;
            c -= k;
        }
        if(c > 0) {
            v[++idx] = a * c;
            w[idx] = b * c;
        }
    }
    
    for(int i = 1; i <= idx; i++)	// 01背包
        for(int j = m; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    
    printf("%d", dp[m]);
    return 0;
}