学步园

学了种很快的新方法，就是每次填f[j]时直接由f[j-weight[i]]推出，前提是num[j - weight[i]]<used[i]
num每填一行都要清零，num[j]表示当前物品填充j大小的包需要至少使用多少个

PS:单调队列和位运算优化http://www.snowoat.tk/?p=161

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define CL(a,b) memset(a,b,sizeof(a))
#define MIN(a,b) (a<b?a:b)
#define INF 0x7ffffff
using namespace std;
const int M(100010);
const int N(110);
int f[M],a[N],v[N],used[M];
int main()
{
	int m,n,i,j,k;
	while(scanf("%d%d",&n,&m)!=EOF&&(n+m))
	{
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		CL(f,0);
		for(i=0;i<n;i++)
			scanf("%d",&v[i]);
		int t;
	/*	m--;
		sum=MIN(sum,m);
		for(i=0;i<n;i++)
		{
			j=1;
			while(j<=a[i])
			{
				t=j*v[i];
				for(k=sum;k>=t;k--)
					f[k]=MAX(f[k],f[k-t]+t);
				a[i]-=j;
				j<<=1;
			}
			t=a[i]*v[i];
			for(k=sum;k>=t;k--)
				f[k]=MAX(f[k],f[k-t]+t);
		}
		t=0;
		for(i=1;i<=sum;i++)
		{
		//	printf("(%d,%d)",i,f[i]);
			if(f[i]==i)
				t++;
		}*/
		f[0]=1;
		for(i=0;i<n;i++)
		{
			CL(used,0);
			for(j=a[i];j<=m;j++)
			{
				int num=j-a[i];
				if(!f[j]&&f[num]&&used[num]<v[i])
				{
					f[j]=1;used[j]=used[num]+1;
				}
			}
			
		}
		t=0;
		for(i=1;i<=m;i++)
			if(f[i])
				t++;
		printf("%d\n",t);

	}
}

//单调队列优化
#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;
    }
}

//位运算优化
#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;
    }
}