http://acm.fzu.edu.cn/problem.php?pid=2214
Accept: 4 Submit: 6Time 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
15
Source
第六届福建省大学生程序设计竞赛-重现赛（感谢承办方华侨大学）
分析:虐的没点脾气，首先B很大，用01背包开数组开不开，然后我就想什么离散化，结果也没搞出来，最后看到题解居然是把价值下的重量，顿时感觉自己弱爆了，可以把价值看作背包容量啊，就是把这个价值装满的最小重量就是那个对应的重量下的最大价值，一点点变性思维就能解决的事，弱爆了
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 }
View Code
转载于:https://www.cnblogs.com/zhaopAC/p/5080696.html
