#include<iostream>
using namespace std;
#define maxn 100001
#define maxn1 220
int m;
void complete_bag(int n,int V,int value[],int weight[],int num[])
{
	int dp[maxn1][maxn];
	int i,j,k,ans=0;;
	for(i=0;i<=n;i++)
		dp[i][0]=0;
	for(j=0;j<=V;j++)
		dp[0][j]=0;
	for(i=1;i<=n;i++)  
		for(j=1;j<=V;j++)
		{
			for(k=0;k<=num[i]&&k*weight[i]<=j;k++)
			{
			   if(j<k*weight[i])
				  dp[i][j]=dp[i-1][j];
			   else
			   {
				if(dp[i-1][j]>dp[i-1][j-k*weight[i]]+k*value[i])
					dp[i][j]=dp[i-1][j];
				else
					dp[i][j]=dp[i-1][j-k*weight[i]]+k*value[i];
			   }
			}
		}
	for(j=1;j<=m&&j<=V;j++)
	 if(dp[n][j]==j)
		  ans++;
	 cout<<ans<<endl;


}

int main()
{
	int n,v,i;
	int value[maxn1],num[maxn1];
	while(cin>>n>>m&&n||m)
	{
	for(i=1;i<=n;i++)
		cin>>value[i];
	v=0;
	for(i=1;i<=n;i++)
	{
		cin>>num[i];
		v+=num[i]*value[i];
	}
	complete_bag(n,v,value,value,num);
	}
	return 0;
}

• Re o(N*V)算法 什么牛逼数据都过了 但交不上 (662) tanyin 2009-08-11 20:21:25