HDU 2844 Coins(多重背包)

刺骨的言语ヽ痛彻心扉 2022-03-31 10:35 190阅读 0赞

[http://acm.hdu.edu.cn/showproblem.php?pid=2844][http_acm.hdu.edu.cn_showproblem.php_pid_2844]

**题意:**

如今有价值val\[1\],val\[2\],…val\[n\]的n种硬币, 它们的数量分别为num\[i\]个. 然后给你一个m, 问你区间\[1,m\]内的全部数目, 由之前n种硬币来构造(**即选取某些硬币使得这些硬币的价值和等于\[1,m\]区间的特定数**), 最多能构造出这m个数中的多少个?

**分析:**

主要的全然背包问题.

我们令dp\[i\]\[j\]==x表示用前i种硬币且硬币总价值总价值正好等于j时, 有多少种方法.

**初始化**: dp为全0,且 dp\[0\]\[0\]==1.

对于每种硬币, 我们有两种可能的方式处理:

1. Val\[i\]\*num\[i\]>= m时, 对当前硬币做一次全然背包就可以.

2. Val\[i\]\*num\[i\]<m时, 我们把当前硬币分成以下k+1类:

1个 2个 4个… 2^(k-1)个, 以及 num\[i\]-2^k+1个

然后我们对上面k+1类物品每一个都做一次01背包就可以, 由于对上面k+1类新物品的01选择会覆盖我们全部可能的对原来第i类物品做的不论什么选择.

**终于所求**: 全部使得dp\[n\]\[j\]!=0 的j值得和. (1<=j<=m)

**AC代码:**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=100000+5;
    
    int n;//物品种数
    int m;//总金钱数
    int cost[100+5];//第i种物品的花费
    int num[100+5]; //第i种物品的数量
    int dp[maxn];
    
    //1次01背包过程
    void ZERO_ONE_PACK(int cost)
    {
        for(int i=m;i>=cost;i--)
            dp[i] += dp[i-cost];
    }
    
    //1次全然背包过程
    void COMPLETE_PACK(int cost)
    {
        for(int i=cost;i<=m;i++)
            dp[i] += dp[i-cost];
    }
    
    //1次多重背包过程
    void MULTIPLY_PACK(int cost,int num)
    {
        if(cost*num>=m)
        {
            COMPLETE_PACK(cost);
            return ;
        }
    
        int k=1;
        while(k<num)
        {
            ZERO_ONE_PACK(cost*k);
            num -= k;
            k*=2;
        }
        ZERO_ONE_PACK(cost*num);
    }
    
    int main()
    {
        while(scanf("%d%d",&n,&m)==2 && n)
        {
            //读取输入+初始化
            for(int i=1;i<=n;i++)
                scanf("%d",&cost[i]);
            for(int i=1;i<=n;i++)
                scanf("%d",&num[i]);
            memset(dp,0,sizeof(dp));
            dp[0]=1;
    
            //递推
            for(int i=1;i<=n;i++)
                MULTIPLY_PACK(cost[i],num[i]);
    
            //统计结果ans
            int ans=0;
            for(int i=1;i<=m;i++)if(dp[i])
                ans++;
            printf("%d\n",ans);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_2844]: http://acm.hdu.edu.cn/showproblem.php?pid=2844