AcWing 5：多重背包问题 II ← 二进制优化
【题目来源】
【题目描述】
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
【输入格式】
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
【输出格式】
输出一个整数，表示最大价值。
【输入样例】
4 5
1 2 3
2 4 1
3 4 3
4 5 2
【输出样例】
10
【数据范围】
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
【算法分析】
● 多重背包问题：有 n 种物品和一个容量为 V 的背包。第 i 种物品有固定体积 vol[i]、固定价值 val[i]，并且最多可以选取 k[i] 件。在总体积不超过背包容量的前提下，选择若干件物品，使得总价值最大。→ 注意：“暴力拆分”的多重背包代码中，物品种数最大为 n×max(k[i])。二进制优化的多重背包代码中，物品种数最大为 n×max(k[i]二进制拆解后的项数)。
● 多重背包中每种物品的数量有限，与物品可无限选取的完全背包约束不同，因此不能转换为完全背包求解。
● 在数据规模不大（≤100）的前提下，可将多重背包中的第 i 种物品按照其最大可选取数量，拆分为若干个相互独立、属性完全一致的单件物品。这样一来，原来的多重背包问题，就变成了每个物品只能选或不选的 0/1 背包问题，可以直接用 0/1 背包的方法求解。
● 若问题规模较大，利用“暴力拆分”的方法会直接将每种物品拆分为若干个独立的单件物品，会使物品数量急剧增多，导致算法时间复杂度过高，在程序运行时极易出现超时（TLE）。所以，对于问题规模较大的多重背包问题，就需要进行二进制优化或单调队列优化。
● 二进制优化：一个正整数 n，可以被分解成 1, 2, 4, …, 2^(k-1), n-2^k+1 的形式。其中，k 是满足 n-2^k+1>0 的最大整数。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
cout<<n<<"=";
int k=1;
while(k<=n) {
if(k==n) cout<<k;
else cout<<k<<"+";
n=n-k;
k=k*2;
}
if(n>0) cout<<n;
return 0;
}
/*
in1:26
out1:26=1+2+4+8+11
in2:7
out2:7=1+2+4
*/
例如：价值为 2、数量为 10 的物品，按二进制优化可拆分为 1、2、4、3 四份，分别对应价值 2、4、8、6，且每组数量均为 1，直接按 0/1 背包处理。
【算法代码】
本题中，每种物品最多 2000 件。依据二进制优化的思想，可将 2000 分解为 2000=1+2+4+…+2^9+C，即每种物品最多拆分成 11 堆。又由于题目给出的物品种数的上限为 1000，因此二进制优化后最多有 11×1000 堆物品（也即多重背包二进制优化后对应的物品总数）。
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e4+5;
int vol[maxn],val[maxn];
int f[maxn];
int n,v,cnt;
int main() {
cin>>n>>v;
for(int i=1; i<=n; i++) {
int volume,value,num;
cin>>volume>>value>>num;
int k=1;
while(k<=num) {
cnt++;
vol[cnt]=volume*k;
val[cnt]=value*k;
num=num-k;
k=k*2;
}
if(num>0) {
cnt++;
vol[cnt]=volume*num;
val[cnt]=value*num;
}
}
for(int i=1; i<=cnt; i++) {
for(int j=v; j>=vol[i]; j--) {
f[j]=max(f[j],f[j-vol[i]]+val[i]);
}
}
cout<<f[v]<<endl;
return 0;
}
/*
in:
4 5
1 2 3
2 4 1
3 4 3
4 5 2
out:
10
*/
【参考文献】
浙公网安备 33010602011771号