注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj3260The Fewest Coins题解  

2014-04-17 22:52:11|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

                                                    最少硬币数
                                             BY   LGS
题目大意:有N种货币,每个货币john有c[i]个,店家有无限个。john要买T元的物品,求最小的找零方案使所用硬币数量最少。

题解:明显的背包,但是上限比较难求,我是看题解才知道的:
给钱上界为:T+maxValue^2,其中maxValue为最大硬币面值。 
证明:反证法。假设存在一种支付方案,John给的钱超过T+maxValue^2,   
则售货员找零超过maxValue^2,则找的硬币数目超过maxValue个,将其看作一数列,  
求前n项和sum(n),根据鸽巢原理,至少有两 个对maxValue求模的值相等,  
假设为sum(i)和sum(j),i<j,则i+1...j的硬币面值和为maxValue的倍数,  
同理,John给的钱中也有 一定数量的硬币面值和为maxValue的倍数,  
则这两堆硬币可用数量更少的maxValue面值硬币代替,产生更优方案。  
确定完毕后,那么john是有限背包(多重背包)F[I],店家是无限背包跑一遍FF[I]。最后答案就在
min(F[I+T]-FF[I]);而多重背包显然朴素是要超时的,所以用二进制优化即可。
多重背包的二进制优化是这样的:对于每个物品能使用的数量,我们不一定要一个、二个、三个、四个这样,我们可以1个、2个、4个、8个。首先每个数一定是可以由这些组成的,就是二进制表示十进制数罢了。那么我们只要枚举这些即可。保证状态不会被遗漏,化成了一堆一堆,效率转换成logN。

总结:混合背包+二进制优化。
代码:
  • Source Code
  • #include<cstdio>
    #include<cstring>
    #define vv 125*125+11000
    #define nn 200
    #define min(a,b) (a>b)?b:a
    #define max(a,b) (a>b)?a:b
    #define INF 999999999
    using namespace std;
    int f[vv],ff[vv];
    int n,t,v,i,j,k,sum,ans,a[nn],c[nn];
    int main()
    {
     scanf("%d%d",&n,&t);v=0;
     for (i=1;i<=n;i++)
         {scanf("%d",&a[i]);v=max(a[i],v);}
     for (i=1;i<=n;i++)
         scanf("%d",&c[i]);
     v=v*v+t;
    memset(f,60,sizeof(f));
    memset(ff,60,sizeof(ff));
    f[0]=0;ff[0]=0;
     for (i=1;i<=n;i++)
      for (j=0;j<=v-a[i];j++)
            f[j+a[i]]=min(f[j+a[i]],f[j]+1);
    
     for (i=1;i<=n;i++)
                 {
                 k=1;
                 sum=0;
                 while (sum<c[i]){
                 for (j=v-a[i]*k;j>=0;j--)
                     ff[j+a[i]*k]=min(ff[j+a[i]*k],ff[j]+k);
                  sum+=k;
                     if (sum+2*k>c[i])
                      k=c[i]-sum;
                      else k*=2;
                                  }
                 }
    ans=INF;
    for (i=t;i<=v;i++)ans=min(ans,ff[i]+f[i-t]);
    if (ans>=INF) printf("-1\n");
    else printf("%d\n",ans);
    return 0;
    }
  评论这张
 
阅读(1380)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018