Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题目链接
题意:容量为V的背包，n个骨头，给出价值和体积，问最多能装多少价值的背包。
思路：01背包裸体。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月16日 星期三 15时14分36秒
4File Name :code/hdu/2602.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E3+7;
34int dp[N],value[N],cost[N];
35int n,V;
36void solve(int v,int c)
37{
38 for ( int i = V; i >= c; i --)
39 dp[i] = max(dp[i],dp[i-c]+v);
40}
41int main()
42{
43 #ifndef ONLINE_JUDGE
44 freopen("code/in.txt","r",stdin);
45 #endif
46 int T;
47 cin>>T;
48 while (T--)
49 {
50 scanf("%d%d",&n,&V);
51 ms(dp,0);
52 for ( int i = 1 ;i <= n ; i++) scanf("%d",&value[i]);
53 for ( int i = 1; i <= n ; i++) scanf("%d",&cost[i]);
54 for ( int i = 1 ; i <= n ; i++) solve(value[i],cost[i]);
55 int ans = 0 ;
56
57 for ( int i = 0 ; i <= V ; i++) ans = max(ans,dp[i]);
58 printf("%d\n",ans);
59 }
60
61 #ifndef ONLINE_JUDGE
62 fclose(stdin);
63 #endif
64 return 0;
65}