这是一道可以用多重背包来写的题，但是这种方法速度很慢，2829MS。思路很简单，将多重背包转化为01背包，dp所对应的下标为钱数，如果能刚好凑到下标所对应的钱数，就赋为1。最后输出被赋为1的个数就是可能性。

#include
     
      #include
      
       #define MAX_PRICE 1000000#define MAX_COIN 110void mk_list(int,int,int);int top=1,stk[MAX_PRICE];int main(){    int n,m;    while(scanf("%d%d",&n,&m)!=EOF&&!(n==0&&m==0))    {    int i,j,val[MAX_COIN],amnt[MAX_COIN],dp[MAX_PRICE];    for(i=1;i<=n;i++)    {        scanf("%d",&val[i]);    }    for(i=1;i<=n;i++)    {        scanf("%d",&amnt[i]);    }    for(i=1,top=1;i<=n;i++)    {        mk_list(val[i],amnt[i],m);    }    for(i=1;i<=m;i++)        dp[i]=0;    dp[0]=1;    int ans=0;    for(i=1;i
       
        =stk[i];j--)        {        if(!dp[j]&&dp[j-stk[i]]==1)        {            dp[j]=1;            ans++;        }        }    }    printf("%d\n",ans);    }    return 0;}void mk_list(int val,int amnt,int m){    int k=1;    while(k
        
         <=m)    {        stk[top++]=k*val;        amnt-=k;        k=k*2;    }    if(val*amnt<=m)    {        stk[top++]=val*amnt;    }}