POJ 1276 Cash Machine


79ms   Cash Machine

多重背包问题:
思想:
  把多重背包问题转化成01背包,假设某件物品的数量上限是n,每件的体积是c,价值是w 
  那么可把该物品分成系数是1,2,4……,2^(k-1), 和n-2^k+1,(k的满足2^k<n)的最大整数
  那么新的物品就是(体积,价值)(1*c,1*w),(2*c,2*w),(4*c,4*w),
            ……(2^k*c,2^k*w),((n-2^k+1)*c,(n-2^k+1)*w)
    例如7可以分成系数为1,2,4。 13得到系数为1,2,4,6的物品。
   这样构造出来的物品和原来数量小于等于n的情况等同,即原来该物品可取的任意数量,可以由这些物品组合得到。
   如比如7那个例子,取6个物品,可由2,4得到。取3个物品可由,1,2得到。
   deal()就是完成这样的任务。
 1 
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<string.h>
 5 using namespace std;
 6 int c[10001]={0};
 7 int dp[100001]={0};  
 8 int i,j,n,cash,npack,bill,num;
 9 
10 void deal(int num, int bill)
11 {
12     int k=0,j,t;
13     if(num==1){ npack++; c[npack]=bill; return ; }
14     if(num==2){ npack++; c[npack]=bill; npack++; c[npack]=bill; return ;}
15     for( k=1,j=2*k; 2*j-1<num; k++,j*=2)  //j==2^k
16                     ;
17     k--;   
18     for(j=1,t=0; t<=k; j*=2,t++)
19     {
20              npack++;
21              c[npack]=j*bill;
22     }
23     npack++;
24     c[npack]=(num-j+1)*bill;
25 }
26 
27 int main()
28 {
29       
30     while(cin>>cash)
31     {
32        memset(dp,0,sizeof dp);
33        memset(c,0,sizeof c);
34        npack=0;  
35        cin>>n;
36        for(i=1; i<=n; i++)
37                { 
38                       cin>>num>>bill;
39                       if(num==0)continue;
40                       deal(num,bill);
41                }
42                
43                
44      
45        dp[0]=1;
46        
47        for(i=1; i<=npack; i++)
48        for(j=cash; j>=c[i]; j--)
49        {
50                    dp[j]= dp[j]||dp[j-c[i]];
51        }
52        
53        for(j=cash; j>=0; j--)
54                   if(dp[j])
55                   {
56                            cout<<j<<endl;
57                            break;
58                   }
59     }
60     system("pause");
61     return 0;
62 }
63 
64 

posted on 2010-08-09 23:52 田兵 阅读(459) 评论(0)  编辑 收藏 引用 所属分类: POJ


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


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜