硬币问题 （dp，多重背包的二分优化）

题目描述

给你n种硬币，知道每种的面值Ai和每种的数量Ci。问能凑出多少种不大于m的面值。

输入

有多组数据，每一组第一行有两个整数 n(1≤n≤100)和m(m≤100000)，第二行有2n个整数，即面值A1，A2，A3，…，An和数量C1，C2，C3，…，Cn (1≤Ai≤100000，1≤Ci≤1000)。所有数据结束以2个0表示。

输出

每组数据输出一行答案。

样例输入

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

样例输出

8
4

背包问题的复杂度是n*m，这题如果直接按照多重背包的计算会超时。所以和上一篇一样，多重背包的二分优化。

　详细的说明在  http://www.cnblogs.com/agenthtb/p/5792628.html

代码如下：

#include <bits/stdc++.h>

using namespace std;

int w[100010],v[20010],maxn=0,dp[100010],n,m,cnt,x;
void f(int weight,int num)//把硬币进行二分的合并
{
    for (int i=1;;i*=2)
    {
        if (num>=i)
        w[cnt++]=weight*i;
        else
        {
            w[cnt++]=num*weight;
            return;
        }
        num-=i;
        if (num<=0)
        return;
    }
}
int main()
{
    //freopen("de.txt","r",stdin);
    while (~scanf("%d%d",&n,&m))
    {
        if (n==0&&m==0)
        break;
        memset(w,0,sizeof w);
        memset(v,0,sizeof v);
        memset(dp,0,sizeof dp);
        dp[0]=1;
        set<int>s;
        cnt=1;
        for (int i=1;i<=n;++i)
        scanf("%d",&v[i]);
        for (int i=1;i<=n;++i)
        {
            scanf("%d",&x);
            f(v[i],x);
        }
        for (int i=1;i<cnt;++i)
        {
            for (int j=m;j>=w[i];--j)
            {
                if (dp[j-w[i]])
                dp[j]=1;
            }
        }
        int ans=0;
        for (int i=1;i<=m;++i)
        if (dp[i]) ans++;
        printf("%d
",ans);
    }
    return 0;
}