问题描述

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

第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

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

输入格式

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

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

输出格式

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

数据范围

$0 \lt N \le 1000$
$0 \lt V \le 2000$
$0 \lt v_i, w_i, s_i \le 2000$

提示：

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

输入样例

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

输出样例：

1
10

题目求解

相比于多重背包问题Ⅰ（详见动态规划 — 多重背包问题Ⅰ）来讲，这道题目的数据范围变大了，导致原来$O(n^3)$的算法求解超时，这道题目考察的是一种二进制拆分状态压缩的思想。

二进制拆分

先看一个简单的例子：问怎样用最少的数字使得这些数字能组合得到$0 \sim 7$之间的所有数字，最简单易想的方案是用$7$个$1$选或者不选就能表示这些数，但是这样拆分出来的份数太多了，和$Ⅰ$中转换成$01$背包解决问题的方案一致，复杂度仍然达到$O(n^3)$。$0 \sim 7$一共八种状态最少使用3个数字选或者不选来表示这些状态，我们可以使用一种二进制的拆分方法，即$1，2，4$这三个数来表示。假设需要表示$0 \sim s$之间的数，如果$s$不是$2^n-1$,比如说$s$是$10$，我们不可以将$10$拆成$1，2，4，8$，这样的话表示的数字范围是$0 \sim 15$，应该拆分为$1，2，4，3$，最后的$3$即为$10 - 1 - 2 - 4$，相当于有了一个$3$的偏移量。总的拆分份数为$ \lceil \log(s) \rceil $。

代码

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 2010;

struct Good {
    int v,w;
};

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

int main() {
    vector<Good> goods;
    cin >> n >> m;
    while(n --) {
        cin >> v >> w >> s;
        for(int k = 1; k <= s; k *= 2) {
            goods.push_back({v * k , w * k});
            s -= k;
        }
        if(s) goods.push_back({v * s, w * s});
    }
    for(auto good : goods) {
        for(int j = m; j >= good.v ;j --) {
            f[j] = max(f[j], f[j - good.v] + good.w);
        }
    }
    cout << f[m] << endl;
    
}