一本通-1267:【例9.11】01背包问题(01背包模板)¶
【题目描述】 一个旅行者有一个最多能装 M 公斤的背包,现在有 n 件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为C1,C2,...,Cn,求旅行者能获得最大总价值。
【输入】 第一行:两个整数,M(背包容量,M≤200)和N(物品数量,N≤30);
第2..N+1行:每行二个整数Wi,Ci,表示每个物品的重量和价值。
【输出】 仅一行,一个数,表示最大总价值。
【输入样例】 10 4 2 1 3 3 4 5 7 9
【输出样例】 12
#include <bits/stdc++.h>
using namespace std;
int volume, n;
vector<int> weight(35), value(35);
vector<int> d(205);
int zeroOnePack()
{
for (int i = 0; i < n; ++i) {
for (int j = volume; j >= weight[i]; --j) {
d[j] = max(d[j], d[j - weight[i]] + value[i]);
}
}
return d[volume];
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> volume >> n;
for (int i = 0; i < n; ++i) {
cin >> weight[i] >> value[i];
}
cout << zeroOnePack() << endl;
return 0;
}