随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    典型的完全背包题。三种不同价值的物品,不限每种商品取得次数,在限定的预订n内,得到的最大价值
 4 How to Do:    f[V]=max{f[V-k*c[i]]+k*c[i]}
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 using namespace std;
 9 int f[10001];
10 int main(){
11     //freopen("in.txt","r",stdin);
12     int t;
13     scanf("%d",&t);
14     while(t--){
15         int m;
16         scanf("%d",&m);
17         int i,j;
18         int c[3]={150,200,350};
19         memset(f,0,sizeof(f));
20         for(i=0;i<3;i++){
21             for(j=c[i];j<=m;j++){
22                 int k=1,max=f[j];
23                 //以下的while循环体是关键代码
24                 while(j-k*c[i]>=0){//测试k值是满足题意的
25                     if((f[j-k*c[i]]+k*c[i])>max&&(f[j-k*c[i]]+k*c[i])<=j)//此处限定的范围很关键
26                         max=f[j-k*c[i]]+k*c[i];
27                     k++;
28                 }
29                 f[j]=max;
30             }
31         }
32         printf("%d\n",m-f[m]);
33     }
34     return 0;
35 }
36 
posted on 2012-03-03 01:21 Leo.W 阅读(453) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理