要求
有n种重量和直接分别为
wi
,
vi的物品。从这些物品中挑选总重量不超过
W$的物品，求出挑选物品的价值总和的最大值。在这里，每种物品可以挑选任意多件
限制条件
(1 <= n <= 100)(1 <=
wi
,
vi
<- 100)(1 <=
W
<script type="math/tex" id="MathJax-Element-76">W</script> <- 10000)
输入格式
第一行输入n 接下来n行输入wi,vi 接下来输入W
输出格式
输出价值总和的最大值
测试输入
3 3 4 4 5 2 3 7
测试输出
10
解题思路
使用dp数组，当前最大值就等于（选i个重量为j和选i个重量为j-w[i]+v[i]中价值最大的）。
代码
#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 <= W; j++) {
if (j < w[i]) {
dp[i +
1][j] = dp[i][j];
}
else {
dp[i +
1][j] = max(dp[i][j], dp[i +
1][j - w[i]] + v[i]);
}
}
}
cout << dp[n][W] << endl;
return 0;
}
