练习题 No.8 完全背包问题

要求

有n种重量和直接分别为 wi , vi的物品。从这些物品中挑选总重量不超过 W$的物品，求出挑选物品的价值总和的最大值。在这里，每种物品可以挑选任意多件

限制条件

• (1 <= n <= 100)
• (1 <= wi , vi <- 100)
• (1 <= W <- 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;  
}