有n个物品，重量和价值分别为wi和vi，从这些物品中挑选出重量不超过W的物品，求所有挑选方案中物品价值总和的最大值
限制条件:
1 <= n <= 100; 1 <= wi<= 10^7; 1 <= vi <= 100; 1 <= W <= 10^9;
分析：数据量更大，之前求解该问题的时间复杂度为o(nW),在这一问题来说会超时，在这个问题里重量很大，但是价值很小，可以考虑价值，改变dp的对象，针对不同的价值来计算最小的质量
因为是求最小值，开始把dp初始化为INF
状态：dp[i][j] = 前i个物品中挑选价值总和为j时的重量最小值
状态转移方程：dp[i+1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
利用翻滚数组即一维数组可以大大节省空间
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF = ;
int dp[];
int w[], v[];
int main() {
int n, W;
while(scanf("%d%d", &n, &W) == ) {
int sum = ;
for(int i = ; i < n; i++) {
scanf("%d%d", &w[i], &v[i]);
sum += v[i];
}
fill(dp, dp + , INF);
dp[] = ;
for(int i = ; i < n; i++) {
for(int j = sum; j >= v[i]; j--) {
dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
}
}
for(int i = sum; i >= ; i--) {
if(dp[i] <= W) {
printf("%d\n", i);
break;
}
}
}
return ;
}