题目描述
给有一个能承重 V 的背包，和n种物品，每种物品的数量有限多，我们用重量、价值和数量的三元组来表示一个物品，第 i 件物品表示为（Vi，Wi，Si），问在背包不超重的情况下，得到物品的最大价值是多少？
输入
第一行输入两个数V、n，分别代表背包的最大承重和物品种类数。
接下来 n 行，每行三个数 Vi、Wi、Si，分别代表第 i 种物品的重量、价值和数量。
输出
输出一个整数，代表在背包不超重情况下所装物品的最大价值。
样例输入1
15 4
4 10 5
3 7 4
12 12 2
9 8 7
样例输出1
37
数据规模与约定
时间限制：1 s
内存限制：64 M
60% 的数据保证(Vi≤V≤1000,n≤100,Si≤10,Wi≤1000)
100% 的数据保证(Vi≤V≤100000,n≤100,Si≤100000,Wi≤1000)
#include <iostream>
using namespace std;
int all, n, ind, w[100005], v[100005], ans[100000];
int main() {
cin >> all >> n;
for (int i = 0; i < n; i++) {
int x, y, z;
cin >> x >> y >> z;
for (int j = 0; j < z; j++) {
ind++;
w[ind] = x;
v[ind] = y;
}
}
for (int i = 1; i <= ind; i++) {
for (int j = all; j >= w[i]; j--) {
ans[j] = max(ans[j], ans[j - w[i]] + v[i]);
}
}
cout << ans[all] << endl;
return 0;
}
二进制优化
#include <iostream>
using namespace std;
int all, n, ind, w[100005], v[100005], ans[100005];
int t[20];
int main() {
int tt = 1;
for (int i = 0; i < 20; i++) {
t[i] = tt;
tt *= 2;
}
cin >> all >> n;
for (int i = 0; i < n; i++) {
int x, y, z, temp = 0;
cin >> x >> y >> z;
while (z > 0) {
ind++;
if (z >= t[temp]) {
w[ind] = x * t[temp];
v[ind] = y * t[temp];
z -= t[temp];
} else {
w[ind] = x * z;
v[ind] = y * z;
z = 0;
}
temp++;
}
}
for (int i = 1; i <= ind; i++) {
for (int j = all; j >= w[i]; j--) {
ans[j] = max(ans[j], ans[j - w[i]] + v[i]);
}
}
cout << ans[all] << endl;
return 0;
}