1384.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"memory.h"
int min[10010];
int value[510],weight[510];
int n,e,f;

void init()
{
	int i;

	scanf("%d %d",&e,&f);
	scanf("%d",&n);

	for(i=0;i<n;i++)
		scanf("%d %d",&value[i],&weight[i]);

	for(i=1;i<=f-e;i++)
		min[i]=99999999;
	min[0]=0;
}

void doit()
{
	int i,j,max;
	for(i=0;i<n;i++)
	{
		max=f-e-weight[i];
		for(j=0;j<=max;j++)
			if(min[j+weight[i]]>min[j]+value[i])
				min[j+weight[i]]=min[j]+value[i];
	}
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		init();
		doit();
		if(min[f-e]==99999999)
			printf("This is impossible.\n");
		else printf("The minimum amount of money in the piggy-bank is %d.\n",min[f-e]);
	}
	return 0;
}