Given 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#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <stack> #include <map> #include <vector> #include <queue> using namespace std; typedef long long LL; #define N 2600000 #define met(a, b) memset(a, b, sizeof(a)) #define INF 0x3f3f3f3f int v[550], w[550]; int dp[N]; int main() { int T; scanf("%d", &T); while(T--) { int i, j, n, B, Max=0, Index; scanf("%d%d", &n, &B); for(i=1; i<=n; i++) { scanf("%d%d", &w[i], &v[i]); Max += v[i]; } for(i=0; i<=Max; i++) dp[i] = INF; dp[0] = 0; for(i=1; i<=n; i++) for(j=Max; j>=v[i]; j--) { dp[j] = min(dp[j], dp[j-v[i]]+w[i]); } for(i=0; i<=Max; i++) if(dp[i]<=B) Index = i; printf("%d\n", Index); } return 0; }
(01背包 当容量特别大的时候) Knapsack problem （fzu 2214）
原文：http://www.cnblogs.com/YY56/p/5509864.html