又见01背包

描述     有n个重量和价值分别为wi 和 vi 的 物品，从这些物品中选择总重量不超过 W  的物品，求所有挑选方案中物品价值总和的最大值。 　　1 <= n <=100 　　1 <= wi <= 10^7 　　1 <= vi <= 100 　　1 <= W <= 10^9 输入 多组测试数据。 每组测试数据第一行输入，n 和 W ，接下来有n行，每行输入两个数，代表第i个物品的wi 和 vi。 输出 满足题意的最大价值，每组测试数据占一行。 样例输入 4 5 2 3 1 2 3 4 2 2 样例输出 7

分析：

题目为正常的01背包思路，但是因为给定的质量的范围1e9,太大了，所以转化思维

普通方法就是直接找最大价值，现在要换种思维，找最小的重量， 因为同样价值，重量越小，那么最后能装的价值就可能越大，所以这个dp[i][j]就表示 当 取 i 个， 价值为j 的时候的最小重量，状态转移方程为 dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - value[i]] + weight[i]), 和那个最初推的一样，不再罗嗦，空间优化之后状态转移方程为dp[j] = min(dp[j], dp[j - value[i]] + weight[i]), 同样的意思，dp[j]表示 价值为j 的时候的最小重量，到最后只要从最大价值往下遍历这个dp数组，只要找到dp[j] <= 背包重量的时候就直接输出 j ， 这时候j就是最大的。

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <vector> #include <set> #include <map> #include <stack> #include <string> using namespace std; struct node { int wi; int vi; }a[105]; int dp[10005]; int main() { int n,w; while(cin >> n >> w) { int wi,vi; int sum = 0; for(int i = 0;i < n;i++) { cin >> a[i].wi >> a[i].vi; sum += a[i].vi; } memset(dp,0x3f3f3f3f,sizeof(dp)); dp[0] = 0; for(int i = 0;i < n;i++) { for(int j = sum;j >= a[i].vi;j--) { dp[j] = min(dp[j],dp[j-a[i].vi]+a[i].wi);///求最小质量，需要初始化为最大 } } for(int i = sum;i >= 0;i--) { if(dp[i] <= w) { cout << i << endl; break; } } } return 0; }