HDU链接
牛客网链接
@[toc]

题目描述：

在这里插入图片描述
输入描述:
在这里插入图片描述
输出描述:

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

输入

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

输出

8
4

题意：

有n种硬币，面额分别是Ai，每种硬币数量分别是Ci，问这些硬币能组成1~m中多少个数？
样例分析：
3 10
1 2 4 2 1 1
有2个一元，1个两元，1个四元，可以组成1,2，3，4,5，6，7,8，（9和10无法组成）能组成的一共八个

题解

如果还没学习背包问题的知识，看这里
混合背包问题
可以用二进制的方法来优化
背包问题中常见的三个元素：体积（所占容量），价值，数量
在本题中，硬币的价值即是体积也是价值A[i]，数量为硬币的数量C[i]
容量上限是m
当ca>m时，也就是一种货币的金额就超过m时，我们可以当做是完全背包，即将这种货币看做无数个，因为货币的数量乘以金额已经超过上限，所以再多也没有影响。这一部分用完全背包的做法
当ca<m时，我们就当做多重背包来做，将多重背包进行二进制优化，用01背包的解法来做
具体看代码：

（代码）

含详细讲解

#include<bits/stdc++.h> 
using namespace std;
const int maxn=1e5+5;
int dp[maxn];
int a[120],c[120];
int n,m;
void zeroone(int cost,int val)
{
    for(int i=m;i>=cost;i--)
    {
        dp[i]=max(dp[i],dp[i-cost]+val);
    }
}
void wanquanbeibao(int cost,int val)
{
    for(int i=cost;i<=m;i++)dp[i]=max(dp[i],dp[i-cost]+val);
}
void cal(int cost,int val,int num)
{
    if(cost*num>=m)wanquanbeibao(cost,val);//完全背包不必考虑数量
    else {
        for(int i=1;i<=num;i<<=1)
        {
            zeroone(i*cost,i*val);//乘以对应的系数 
            num-=i; 
        }
        zeroone(num*cost,num*val);//剩余部分处理 
    } 
}
int main()
{
    while(cin>>n>>m&&(n+m))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>c[i];
        for(int i=1;i<=n;i++)
        {
            cal(a[i],a[i],c[i]);//花费，价值，数量 
        }
        int sum=0;
        for(int i=1;i<=m;i++)
        {
            if(dp[i]==i)sum++;
        }
        cout<<sum<<endl;
    }
    return 0;
}