http://acm.fzu.edu.cn/problem.php?pid=2214
Problem DescriptionGiven a set of n items, each with a weight w[i] and a value v[i], determine a way to choose the items into a knapsack so that the total weight is less than or equal to a given limit B and the total value is as large as possible. Find the maximum total value. (Note that each item can be only chosen once).
InputThe first line contains the integer T indicating to the number of test cases.
For each test case, the first line contains the integers n and B.
Following n lines provide the information of each item.
The i-th line contains the weight w[i] and the value v[i] of the i-th item respectively.
1 <= number of test cases <= 100
1 <= n <= 500
1 <= B, w[i] <= 1000000000
1 <= v[1]+v[2]+...+v[n] <= 5000
All the inputs are integers.
OutputFor each test case, output the maximum value.
Sample Input Sample Output Source
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int INF = 0x3f3f3f3f; 7 long long thing[5500]; 8 int w[550],v[550]; 9 int main() 10 { 11 int t,n,B; 12 scanf("%d", &t); 13 while(t--) 14 { 15 int sum = 0; 16 scanf("%d%d", &n,&B); 17 for(int i = 1; i <= n; i++) 18 { 19 scanf("%d%d", &w[i], &v[i]); 20 sum += v[i]; 21 } 22 memset(thing, INF, sizeof(thing)); 23 thing[0] = 0; 24 for(int i = 1; i <= n; i++) 25 { 26 for(int j = sum; j >= v[i]; j--) 27 { 28 if(thing[j - v[i]] != INF) 29 thing[j] = min(thing[j], thing[j - v[i]] + w[i]); 30 } 31 } 32 for(int i = sum; i >= 0; i--) 33 { 34 if(thing[i] <= B) 35 { 36 printf("%d\n",i); 37 break; 38 } 39 } 40 } 41 return 0; 42 }
FOJProblem 2214 Knapsack problem（01背包+变性思维）
原文：http://www.cnblogs.com/zhaopAC/p/5080696.html
