学步园

大意不再赘述。

思路：多重背包，POJ上的那道题须用单调队列写，慢慢学，这道题的数据要水很多，所以随便也过了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

const int INF = 0x3f3f3f3f;

int num[110];
int V[110];
int f[101000];

int n, m, C;

void init()
{
	memset(f, -INF, sizeof(f));
	f[0] = 0;
}

void Zp(int cost, int weight)
{
	for(int v = C; v >= cost; v--)
	{
		f[v] = max(f[v], f[v-cost]+weight);
	}
}

void Cp(int cost, int weight)
{
	for(int v = cost; v <= C; v++)
	{
		f[v] = max(f[v], f[v-cost]+weight);
	}
}

void Mp(int cost, int weight, int amount)
{
	if(cost * amount >= C)
	{
		Cp(cost, weight);
		return ;
	}
	else
	{
		int k = 1;
		while(k < amount)
		{
			Zp(k*cost, k*weight);
			amount -= k;
			k *= 2;
		}
		Zp(cost*amount, weight*amount);
	}
}

void dp()
{
	init();
	C = m;
	for(int i = 1; i <= n; i++)
	{
		Mp(V[i], V[i], num[i]);
	}
}

int read_case()
{
	scanf("%d%d", &n, &m);
	if(!n && !m) return 0;
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &V[i]);
	}
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &num[i]);
	}
	return 1;
}

void solve()
{
	dp();
	int count = 0;
	for(int i = 1; i <= m; i++) if(f[i] >= 0) count++;
	printf("%d\n", count);
}

int main()
{
	while(read_case())
	{
		solve();
	}
	return 0;
}