HDU 2844 Coins【多重背包】

HDU 2844 Coins【多重背包】。

Problem Description

Whuacmers use coins.They have coins of value A1,A2,A3…An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn’t know the exact price of the watch.

You are to write a program which reads n,m,A1,A2,A3…An and C1,C2,C3…Cn corresponding to the number of Tony’s coins of value A1,A2,A3…An then calculate how many prices(form 1 to m) Tony can pay use these coins.

Input

The input contains several test cases. The first line of each test case contains two integers n(1 ≤ n ≤ 100),m(m ≤ 100000).The second line contains 2n integers, denoting A1,A2,A3…An,C1,C2,C3…Cn (1 ≤ Ai ≤ 100000,1 ≤ Ci ≤ 1000). The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

Sample Output

8
4

题意：
给你一些不同价值和一定数量的硬币，手表最贵m元，求用这些硬币可以组合成价值在[1 , m]之间的有多少。（和前几道多重背包是不一样的比如hdu2191，求的是最靠近m的组成方式数目）
想法：
整体就是三个背包模板，写下来就是了，最后判断在价值范围的自增就可以了。
比赛用多重背包模板交的这题，一直tle，刚刚补的时候测试数据对了又一直wa，最后发现完全背包的初始化写错了（被自己蠢哭）

#include
#include
#include
#include
using namespace std;
const int maxn=1e5+10;
int dp[maxn],mon[maxn],num[maxn];
int numgiven;
void zeroonepack(int cost,int weight)
{
    for(int i=numgiven;i>=cost;--i)
        dp[i]=max(dp[i],dp[i-cost]+weight);
}
void completepack(int cost,int weight)
{
    for(int i=cost;i<=numgiven;++i)//就是这里！初始值是cost！才不是什么1呢！
        dp[i]=max(dp[i],dp[i-cost]+weight);
}
void multiplepack(int cost,int weight,int cnt)
{

    if(numgiven<=cnt*cost)
        completepack(cost,weight);
    else
    {   
        int k=1;
        while(k<=cnt)
        {
            zeroonepack(k*cost,k*weight);
            cnt-=k;
            k<<=1;
        }
    }
    if(cnt)
        zeroonepack(cnt*cost,cnt*weight);
}
int main()
{
    int n,sum;
    while(~scanf("%d %d",&n,&numgiven),n+numgiven)
    {
        for(int i=1;i<=n;++i)
            scanf("%d",&mon[i]);
        for(int i=1;i<=n;++i)
            scanf("%d",&num[i]);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;++i)
            multiplepack(mon[i],mon[i],num[i]);
        sum=0;
        for(int i=1;i<=numgiven;++i)
        {
            if(dp[i]==i)
                sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}

ps:比赛用多重背包模板交的这题，一直tle，刚刚补的时候测试数据对了又一直wa，最后发现完全背包的初始化写错了（被自己蠢哭）