1031.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1031 on 2005-09-25 at 17:27:41 */ 
#include <stdio.h>
#include <memory.h>
#define  MAXNUM 60000
#define  INFINITE  60000000

int main()
{
	int E, F, N, T;
	int P[500], W[500];
	int i, j, k;
	long value[MAXNUM];
	
	scanf("%d", &T);
	for(i = 0; i < T; i++) {
		scanf("%d %d", &E, &F);
		F -= E;
		scanf("%d", &N);
		for(j = 0; j < N; j++) {
			scanf("%d %d", &P[j], &W[j]);
		}
		value[0] = 0;
		for(j = 1; j <= F; j++) {
			value[j] = INFINITE;
		}
		for(k = 0; k < N; k++) {
			for(j = W[k]; j <= F; j++) {
				if(value[j-W[k]] + P[k] < value[j]) {
					value[j] = value[j-W[k]] + P[k];
				}
			}
		}
		if(value[F] != INFINITE) {
			printf("The minimum amount of money in the piggy-bank is %ld.\n", value[F]);
		} else {
			printf("This is impossible.\n");
		}
	}

	return 0;
}