题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
10
算法
二进制拆分(300+ms)
emm,为啥跑得比单调队列优化的快,你们单调队列都跑多快?
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)2e4+5;
int val[maxn],cst[maxn],sze[maxn],N,V;
int dp[maxn];
void ZeroOnePack (int cost, int value) { //01背包
for (int i = V; i >= cost; i--) {
dp[i] = max(dp[i], dp[i-cost]+value);
}
}
void CompletePack (int cost, int value) { //完全背包
for (int i = cost; i <= V; i++) {
dp[i] = max(dp[i], dp[i-cost]+value);
}
}
void MultiplePack (int idx) { //多重背包
if (sze[idx]*cst[idx] >= V) {
CompletePack(cst[idx], val[idx]);
return ;
}
int x = 1;
int num = sze[idx];
while (x <= num) {
ZeroOnePack(x*cst[idx], x*val[idx]);
num -= x; //拆为多个二进制数
x <<= 1;
}
if (num > 0) {
ZeroOnePack(num*cst[idx], num*val[idx]);
}
}
int main() {
cin >> N >> V;
for (int i = 0; i < N; i++) {
cin >> cst[i] >> val[i] >> sze[i];
}
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++) {
MultiplePack(i);
}
cout << dp[V] << endl;
return 0;
}
我的二进制优化模板230+ms,数据好像不够强
多重背包函数里的完全背包,是因为最大数量乘单位体积大于最大容量了吗,等价于无限选???有点强啊!!!