HDU 2844 Coins 【多重背包】（模板）

<题目连接>

题目大意：

一位同学想要买手表，他有n种硬币，每种硬币已知有num[i]个。已知手表的价钱最多m元，问她用这些钱能够凑出多少种价格来买手表。

解题分析：

很明显，这是一道多重背包的问题，下面是用二进制拆分的多重背包的万能模板。

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int n,m,val[],cnt[],dp[int(1e5+)];

void OneZeroPack(int m,int v,int value){       //01背包

    for(int i=m;i>=v;i--)

        dp[i]=max(dp[i],dp[i-v]+value);

}

void CompletePack(int m,int v,int value){      //完全背包

    for(int i=v;i<=m;i++)

        dp[i]=max(dp[i],dp[i-v]+value);

}

void MultiplePack(int m,int v,int value,int num){

    if(v*num>=m) { CompletePack(m,v,value); return; }    //如果这些物品总体积大于容量，当成完全背包计算

    for(int k=;k<=num;k<<=){        //否则当成01背包，但是对这些物品进行二进制拆分

        OneZeroPack(m,v*k,value*k);

        num-=k;

    }

    if(num)OneZeroPack(m,v*num,value*num);

}

int main(){

    while(~scanf("%d%d",&n,&m),n||m){

        for(int i=;i<=m;i++)dp[i]=-INF;

        for(int i=;i<n;i++)scanf("%d",&val[i]);

        for(int i=;i<n;i++)scanf("%d",&cnt[i]);

        dp[]=;

        for(int i=;i<n;i++)

            MultiplePack(m,val[i],val[i],cnt[i]);

        int ans=;

        for(int i=;i<=m;i++)

            if(dp[i]>)ans++;

        printf("%d\n",ans);

    }

}

另一种方法：

#include <cstdio>

#include <cstring>

bool dp[];

int use[];//i元钱时某种钱用的次数

int n, m;

int val[], num[];

void solve()

{

    memset(dp, , sizeof(dp));

    dp[] = ;

    int count = ;

    for (int i = ; i <= n; i++)    //此题解法就是，现将每一个物品*（1~num[i]）所能达到的价格都标记

    {

        memset(use, , sizeof(use));        //每次初始化第i种钱用了0次

        for (int j = val[i]; j <= m; j++)   //顺序枚举钱数

        {

            if (dp[j - val[i]] && !dp[j] && use[j - val[i]] < num[i])

            {

                dp[j] = ;      //如果钱数为i的情况记录过了，那么就标记，防止count重复+1

                use[j] = use[j - val[i]] + ;//到达j元用的i种钱的次数是到达 j-val[i]元用的次数加1

                count++;

            }

        }

    }

    printf("%d\n", count);

}

int main()

{

    while (~scanf("%d %d", &n, &m),n||m)

    {

        for (int i = ; i <= n; i++)

            scanf("%d", &val[i]);

        for (int i = ; i <= n; i++)

            scanf("%d", &num[i]);

        solve();

    }

    return ;

}