首页 > 其他 > 详细

hdu2844 Coins -----多重背包+二进制优化

时间:2019-04-22 20:27:55      阅读:79      评论:0      收藏:0      [点我收藏+]

题目意思:给出你n种硬币的面额和数量,询问它能够组合成1~m元中的几种情况。

这题如果直接按照完全背包来写的话,会因为每一种硬币的数目1 ≤ Ci ≤ 1000而超时,所以这里需要运用二进制优化来解决问题。

二进制优化和快速幂的思路是一样的。

例如:面值为1的硬币有20枚,如果完全背包的话就需要20次状态转移。

运用二进制优化后,就变成了 面值为1的硬币1枚、面值为2的硬币1枚、面值为4的硬币1枚、面值为8的硬币1枚,最后多出的5个,就直接作为面值为5的硬币一枚,加入新的数组中。之前的20次转移就被优化成了5次。在极限数据1000的情况下优化的更多。

以下为详细代码:

#include<iostream>
#include<string.h>
using namespace std;
int n,m,i,j;
int a[100050],c[100050],s[100050],dp[100050];
int ys=0;
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        ys=0;
        for(i=0;i<n;i++) scanf("%d",&a[i]);
        for(i=0;i<n;i++) scanf("%d",&c[i]);
        for(i=0;i<n;i++)
        {
            int k=1;
            int p=c[i];
            while(p>k)
            {
                s[ys]=a[i]*k;
                ys++;
                p-=k;
                k*=2;
            }
            s[ys++]=a[i]*p;
        }
    //for(i=0;i<ys;i++) cout<<s[i]<<" ";cout<<endl;
    for(i=0;i<=m;i++) dp[i]=0;
    for(i=0;i<ys;i++)
    for(j=m;j>=s[i];j--)
    {
        dp[j]=max(dp[j],dp[j-s[i]]+s[i]);
    }
    int ans=0;
    for(i=1;i<=m;i++) 
    {
    //    cout<<dp[i]<<endl;
        if(dp[i]==i) ans++;
    }
    cout<<ans<<endl;
    }
    
}

 

hdu2844 Coins -----多重背包+二进制优化

原文:https://www.cnblogs.com/wsblm/p/10752252.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!