题目链接：Knapsack problem
大意：给出T组测试数据，每组给出n个物品和最大容量w.然后依次给出n个物品的价值和体积。
问，最多能盛的物品价值和是多少？
思路：01背包变形，因为w太大，转而以v为下标，求出价值对应的最小体积，然后求出能够满足给出体积的最大价值。
经典题目，思路倒是挺简单的，就是初始化总觉得别扭...T_T大概，因为我要找的是最小值，所以初始化为maxn，就结了？
这个问题好像叫01背包的超大背包...
模拟一下样例吧!
1
5 15 // 初始化为dp[0] = 0;
for (int i=0; i<5; ++i) // tot = 29
w v
12 4 i = 0 // dp[4] = 12;
2 2 //dp[6] = 14; dp[4] = 12; dp[2] = 2;
1 1 // dp[7] = 15; dp[5] = 13; dp[3] = 3; dp[1] = 1;
4 10 // dp[17] = 19; dp[15] = 17; dp[13] = 7; dp[11] = 5; dp[10] = 4;
1 2 // dp[19] = 20; dp[17] = 18; dp[15] = 8; dp[13] = 6; dp[12] = 5;
应该是每次放第i个东西的时候，都是在第i-1个的基础上，当当前容量-当前物品的差的容量已经被更新过，当前容量才有可能继续被更新的。
每个东西的容量都是由前一个推导出来的。
附代码：
#include <stdio.h>
#include <string.h>
#include <iostream>
#define inf 1000000000
using namespace std; int v[1010], w[1010];
int dp[5050]; // dp[i] 表示价值为i的时候 重量最小是多少 int main() {
int t;
cin >> t;
while(t--) {
int n, totw;
cin >> n >> totw;
int tot = 0; for (int i=0; i<n; ++i) {
cin >> w[i] >> v[i];
tot += v[i];
} // 初始化？
for (int i=0; i<=tot; ++i) {
dp[i] = inf;
}
dp[0] = 0; for (int i=0; i<n; ++i) {
for (int j=tot; j>=v[i]; --j) {
dp[j] = min(dp[j], dp[j-v[i]]+w[i]);
}
} for (int i=tot; i>=0; --i) {
if (dp[i] <= totw) {
cout << i << endl;
break;
}
}
}
return 0;
}