随笔-65  评论-6  文章-0  trackbacks-0
 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 阅读(109) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理