随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    计算在得到背包最大价值的同时,可能得到的其他值,按严格递减次序,不允许有重复。    
 4 How to Do:    关键是抽出新序列进行排序,更新f[j][k]的信息;
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10 int f[1005][35],temp[65];
11 int w[105],c[105];
12 int main(){
13     int t;
14     //freopen("in.txt","r",stdin);
15     scanf("%d",&t);
16     while(t--){
17         int n,vol,K;
18         scanf("%d%d%d",&n,&vol,&K);
19         int i,j,k;
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                 int cns=0;
26                 for(k=0;k<K;k++){
27                     temp[cns++]=f[j][k];
28                     temp[cns++]=f[j-c[i]][k]+w[i];
29                 }
30                 sort(temp,temp+cns);
31                 int p=0;
32                 for(k=cns-1;k>=0;k--){
33                     if(p>=K)    break;
34                     if(k==cns-1||temp[k]!=temp[k+1])
35                         f[j][p++]=temp[k];
36                 }
37             }
38         }
39         printf("%d\n",f[vol][K-1]);
40     }
41     return 0;
42 }
43 
posted on 2012-03-13 14:58 Leo.W 阅读(334) 评论(0)  编辑 收藏 引用

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