主要思想:二进制分解
优化原理:通过二进制分解省去了很多重复背包组合的计算,因此得以加速。
时间复杂度:$O(V\sum_i{\log M_i})$,其中$M_i$为第$i$种物品的数量。
// 背包九讲里的实现
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2003;
int N, V;
int v[MAX], w[MAX], s[MAX];
int f[MAX];
void solve_01(int vi, int wi) {
// 注意! 01背包是逆序
for (int v = V; v >= vi; --v)
f[v] = max(f[v], f[v - vi] + wi);
}
void solve_complete(int vi, int wi) {
// 注意! 完全背包是正序
for (int v = vi; v <= V; ++v)
f[v] = max(f[v], f[v - vi] + wi);
}
int main() {
cin >> N >> V;
for (int i = 1; i <= N; ++i)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= N; ++i) {
int M = s[i]; // 第i个物品数目
if (M * w[i] >= V)
solve_complete(v[i], w[i]);
else {
int k = 1;
while (k <= M) {
solve_01(k * v[i], k * w[i]);
M -= k;
k *= 2;
}
solve_01(M * v[i], M * w[i]);
}
} // i
cout << f[V] << endl;
return 0;
}