我要啦免费统计
http://acm.pku.edu.cn/JudgeOnline/problem?id=1276
将第i种面额分成若干面额的bill,这些bill面额为 系数1,2,4,。。。。2^(k-1),n[i]-2^k+1 分别乘以d[i] , 并且n[i]-2^k+1>0;
(我也是看别人的,找个数试一下就知道了,用这些面额系数就可以,就可以组成<=n[i]的所有可能)

O(V* S log n[i])

f[v]表示容量v所能得到的总数
简化方程:  f[v]=max{f[v],f[v-c]+c}
f[]初始都为0

 多重背包 详见背包九讲

#include<iostream>
using namespace std;
#define MAXN 120005  //maxcash
#define  MAX 11
int n[MAX],d[MAX];
int f[MAXN];
int V,N;

 
void ZeroOnePack(int c){
     
for(int v=V;v>=c;--v){
      f[v]
=max(f[v],f[v-c]+c);
     }

     
return;
 }

 
void CompletePack(int c){
    
for(int v=c;v<=V;++v){
       f[v]
=max(f[v],f[v-c]+c);
    }

    
return;
 }

 
 
void MultiplePack(int c,int amount){
 
     
if(c*amount>=V){
        CompletePack(c);
       
return;      
     }

     
int k=1;
     
while(k<amount){
        ZeroOnePack(k
*c);
        amount
-=k;
        k
*=2;
     }

     ZeroOnePack(amount
*c);
     
return;
 }

 
 
int main()
 
{
     
int a,b;
     
     
while(scanf("%d%d",&V,&N)!=EOF){
        
if(!V&&!N)continue;
        
int flag=0;
        
for(int i=0;i<=V;++i)f[i]=0;
        
//  memset(f,0,sizeof(f));
        for(int i=0;i<N;++i){
            scanf(
"%d%d",&a,&b);
            n[i]
=a,d[i]=b;
            
if(d[i]==V){f[V]=V;flag=1;}
        }

          
if(V==0)f[V]=0,flag=1;
        
if(!flag){
          
for(int i=0;i<N;++i)
            
if(n[i]&&d[i]<=V)
               MultiplePack(d[i],n[i]);         
         }

         printf(
"%d\n",f[V]);
     }
 
     
return 0;
 }



posted on 2009-03-18 22:42 阅读(1240) 评论(2)  编辑 收藏 引用 所属分类: Dynamic programming

评论:
# re: pku Cash Machine 多重背包 2010-12-21 10:32 | _飞寒
你好、、 这道题目用二进制压缩不超时是吧,我想用单调队列实现v*m复杂度的,请问有代码参考下么。。。  回复  更多评论
  
# re: pku Cash Machine 多重背包 2011-02-17 14:52 | 蔡东赟
@_飞寒
这玩意我都忘了差不多了。 没时间帮你的。 不好意思  回复  更多评论
  

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