FZU 2214 Knapsack problem （超大容量背包）

FZU 2214 Knapsack 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 <= 1001 <= n <= 5001 <= B, w[i] <= 10000000001 <= v[1]+v[2]+…+v[n] <= 5000All the inputs are integers.

Output

For each test case, output the maximum value.

Sample Input

15 1512 42 21 14 101 2

Sample Output

15

题意

n 件物品放入容量为 B 的背包，每件物品都有它的权重和体积，问所能获得的最大权值。

思路

一眼看去只是普通的 01背包，然而数据范围让人无法下手。

之前我们考虑前 i 件物品装入容量为 v 的背包所能获得的最大价值，换位思考一下，我们考虑前 i 件物品组成价值为 w

AC 代码

#include #include#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);using namespace std;typedef long long LL;const int maxn = 1e5+10;const int mod = 998244353;const int inf = 0x3f3f3f3f;LL n,b;LL w[maxn],v[maxn];LL dp[5100];void solve(){ memset(dp,inf,sizeof(dp)); dp[0] = 0; for(int i=1; i<=n; i++) for(int j=5000; j>=v[i]; j--) dp[j] = min(dp[j],dp[j-v[i]]+w[i]); for(int i=5000; i>=0; i--) if(dp[i]<=b) { cout<>T; while(T--) { cin>>n>>b; for(int i=1; i<=n; i++) cin>>w[i]>>v[i]; solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。