源代码在这里面http://www.snowoat.tk/?p=161
单调队列的代码：
Memory: 332K
Time: 2125MS
#include"iostream"
using namespace std;
int main()
{
    int n,m;
    int A[100],C[100];
    char dp[100010];
    while(scanf("%d%d",&n,&m)&&n!=0&&m!=0)
    {
        for(int i=0;i<n;i++)scanf("%d",&A[i]);
        for(int i=0;i<n;i++)scanf("%d",&C[i]);
        memset(dp,0,sizeof(dp));dp[0]=1;
        for(int i=0;i<n;i++)
        {
            if(A[i]>m)continue;
			if(A[i]*C[i]>=m)for(int j=A[i];j<=m;j++)dp[j]=dp[j]|dp[j-A[i]];
			else
            {
				int t=A[i]*C[i]; 
				for(int j=0;j<A[i];j++)
				{
					int sum=0,x=m-j;
					//用C[i]循环出错，虽然A[i]*C[i]<m但是可能A[i]*C[i]+A[i]-1>=m 
					for(;x>=max(0,m-j-t);x-=A[i]){sum+=dp[x];}
					for(int k=m-j;k>0;k-=A[i]){
						sum-=dp[k];dp[k]=sum>0||dp[k];
						if(x>=0){sum+=dp[x];x-=A[i];}
					}
				}
            }
        }
        int cnt=0;
        for(int i=1;i<=m;i++)
            if(dp[i])cnt++;
        cout<<cnt<<endl;
    }
}
二进制的代码：
Memory: 332K
Time: 2375MS
#include"iostream"
using namespace std;
int main()
{
    int n,m;
    int A[100],C[100];
    char dp[100010];
    while(scanf("%d%d",&n,&m)&&n!=0&&m!=0)
    {
        for(int i=0;i<n;i++)scanf("%d",&A[i]);
        for(int i=0;i<n;i++)scanf("%d",&C[i]);
        memset(dp,0,m+1);dp[0]=1;
        for(int i=0;i<n;i++)
        {
            if(A[i]>m)continue;
			if(A[i]*C[i]>=m)for(int j=A[i];j<=m;j++)dp[j]=dp[j]|dp[j-A[i]];
			else
            {
                int k=0,temp;
                while((1<<k)<C[i])
                {
                    temp=A[i]<<k;
                    for(int j=m;j>=temp;j--)dp[j]=dp[j]|dp[j-temp];
                    C[i]-=(1<<k);
                    k++;
                }
                temp=C[i]*A[i];
                for(int j=m;j>=temp;j--)dp[j]=dp[j]|dp[j-temp];
            }
        }
        int cnt=0;
        for(int i=1;i<=m;i++)
            if(dp[i])cnt++;
        cout<<cnt<<endl;
    }
}