练习题 No.9 01背包问题

要求

有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;  
}