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) 编辑 收藏 引用