1 /*
2 Author: Leo.W
3 Descriptipn: 一个容量为V的大包,装价值为m1,体积为v1的物品(m2,v2;m3,v3;mn,vn),
4 共n种物品,每种限取一个,试求得到最大价值。
5 How to Do: f[V]=max{f[V],f[V-c[i]]+w[i]}
6 */ 7 #include <iostream>
8 #include <
string.h>
9 using namespace std;
10 #define MAXSIZE 1002
11 int c[MAXSIZE],w[MAXSIZE],f[MAXSIZE];
12 int main(){
13 //freopen("in.txt","r",stdin);
14 int t;
15 scanf("%d",&t);
16 while(t--){
17 int n,vol;
18 scanf("%d%d",&n,&vol);
19 int i,j;
20 for(i=0;i<n;i++) scanf("%d",&w[i]);
//价值
21 for(i=0;i<n;i++) scanf("%d",&c[i]);
//体积
22 memset(f,0,
sizeof(f));
23 for(i=0;i<n;i++){
24 for(j=vol;j>=c[i];j--){
25 f[j]=f[j]>(f[j-c[i]]+w[i])?f[j]:(f[j-c[i]]+w[i]);
26 }
27 }
28 printf("%d\n",f[vol]);
29 }
30 return 0;
31 }
posted on 2012-03-03 01:23
Leo.W 阅读(137)
评论(0) 编辑 收藏 引用