NYOJ-860-又见01背包

时间限制： 1000 ms  |  内存限制： 65535 KB 难度： 3 描述     有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 解题思路：因为物体重量太大，所以用价值来开dp数组，dp方程为让同等价值的重量尽量小，应初始化为无穷大， dp[0] = 0;

#include <stdio.h>#include <algorithm>#include <string.h>int dp[10005];int main(){ using namespace std; int v[105],w[105]; int n,W; int max_v; while(~scanf("%d%d",&n,&W)){ memset(dp,0x3f,sizeof(dp)); max_v = 0; for(int i=0; i<n; i++){ scanf("%d%d",&w[i],&v[i]); max_v += v[i]; } dp[0] = 0; for(int i=0; i<n; i++){ for(int j=max_v; j>=v[i]; j--){ dp[j] = min(dp[j-v[i]]+w[i] , dp[j]); } } for(int i=max_v; i>=0; i--){ if(dp[i] <= W){//第一个大于W的i一定是最大的价值（i）; printf("%d\n",i); break; } } } return 0;}