要求
有n个背包和价值分为
wi
,
vi
的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
限制条件
(1 <= n <= 100)(1 <=
wi
<=
107
)(1 <=
vi
<= 100)(1 <= W <=
109
)
输入格式
第一行输入n
接下来n行的物品（w,v）
最后输入一行w
输出格式
输出一行价值总和的最大值
测试输入
4
2 3
1 2
3 4
2 2
5
测试输出
7
解题思路
用dp来存w的值，
j来存价值
代码
#include <iostream>
using namespace std;
int dp[
101][
10001];
int main() {
int n;
cin >> n;
int v[
101],w[
101];
for (
int i =
0; i < n; i++) {
cin >> w[i] >> v[i];
}
int W;
cin >> W;
for (
int i =
0; i < n; i++) {
for (
int j =
0; j <
10001; j++) {
dp[i][j] =
0x7f7f7f7f;
}
}
dp[
0][
0] =
0;
for (
int i =
0; i < n; i++) {
for (
int j =
0; j <
10001; j++) {
if (j < v[i]) {
dp[i +
1][j] = dp[i][j];
}
else {
dp[i +
1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
}
int res =
0;
for (
int i =
0; i <
10001; i++) {
if (dp[n][i] <= W) {
res = i;
}
}
cout << res << endl;
return 0;
}
