学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2844

求背包能装满的情况的条数，参见背包九讲，二进制优化完全背包和多重背包问题

#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <iostream>
using namespace std;
const int maxn = 100100;
int dp[maxn];
int n,m,value[150],num[150];
int main(){
    int i,j,k,now,pri,ans;
    while(scanf("%d%d",&n,&m),m+n){
        for(i=1;i<=n;i++)
        scanf("%d",&value[i]);
        for(i=1;i<=n;i++)
        scanf("%d",&num[i]);
        for(i=0;i<=m;i++) dp[i]=-2000000000;
        dp[0]=0;
        for(i=1;i<=n;i++){
            now=1;
            while(now<=num[i]){
                pri=now*value[i];
                for(j=m;j>=pri;j--)
                dp[j]=max(dp[j],dp[j-pri]+pri);
                num[i]-=now;
                now*=2;
            }
            pri=num[i]*value[i];
            if(pri==0) continue;
            for(j=m;j>=pri;j--) dp[j]=max(dp[j],dp[j-pri]+pri);
        }
        ans=0;
        for(i=1;i<=m;i++)
        if(dp[i]==i) ans++;
        printf("%d\n",ans);
    }
    return 0;
}