FZUOJ 2214 Knapsack problem 背包

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2214

题目大意：背包大小为B，问能装下的最大价值。1 <= B, w[i] <= 1000000000

解题思路：由于背包大小太大，因此无法按照重量选择，可以按照价值选择。

dp[i][j]:=前i个物品选价值为j的重量最小值

dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i]] )

当然也可以优化空间复杂度，那么的话对j的循环需要从maxv到v[i]。

代码：

 1 const int inf = 0x3f3f3f3f;
 2 const int maxn = 1e4 + 5;
 3 int v[505], w[505], n, maxv;
 4 ll dp[maxn], B;
 5 
 6 void solve(){
 7     for(int i = 1; i <= maxv; i++) dp[i] = 1e17;
 8     dp[0] = 0;
 9     for(int i = 1; i <= n; i++){
10         for(int j = maxv; j >= v[i]; j--){
11             dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
12         }
13     }
14     ll ans = inf;
15     for(int i = maxv; i >= 0; i--){
16         if(dp[i] <= B) {
17             ans = i; break;
18         }
19     }
20     printf("%lld
", ans); 
21 }
22 int main(){
23     int T;
24     scanf("%d", &T);
25     while(T--){
26         maxv = 0;
27         scanf("%d %d", &n, &B);
28         for(int i = 1; i <= n; i++) {
29             scanf("%d %d", &w[i], &v[i]);
30             maxv += v[i];
31         }
32         solve();
33     }
34 }

题目：

Problem 2214 Knapsack problem

Accept: 666 Submit: 2504
Time Limit: 3000 mSec Memory Limit : 32768 KB

Problem Description

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).

Input

The 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.

Output

For each test case, output the maximum value.

Sample Input

1 5 15 12 4 2 2 1 1 4 10 1 2

Sample Output

Source

第六届福建省大学生程序设计竞赛-重现赛（感谢承办方华侨大学）