pku1384.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
int E, F, W;
int p[510], w[510];
int v[10001];

void Solve()
{
	int n, i, j;
	scanf("%d %d", &E, &F);
	W = F - E;
	scanf("%d", &n);
	memset(v, -1, sizeof(v));
	for (i = 0; i < n; i++)
	{
		scanf("%d %d", &p[i], &w[i]);
	}
	v[0] = 0;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j <= W; j++)
		{
			if ((j - w[i] >= 0) && v[j - w[i]] != -1)
			{
				if (v[j] == -1 || v[j] > v[j - w[i]] + p[i])
				{
					v[j] = v[j - w[i]] + p[i];
				}
			}
		}
	}
	if (v[W] == -1)
	{
		printf("This is impossible.\n");
	}
	else
	{
		printf("The minimum amount of money in the piggy-bank is %d.\n", v[W]);
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		Solve();
	}
	return 0;
}