HDU - 1114 Piggy-Bank

題意：完全背包的變形

#include 
#include 
#include 
#include 
using namespace std;

int f[10010],cost[510],w[510];
int a,b,n;

int main(){
	int t;
	scanf("%d",&t);
	while (t--){
		scanf("%d%d",&a,&b);
		int m = b - a;
		scanf("%d",&n);
		for (int i = 0; i < n; i++)
			scanf("%d%d",&w[i],&cost[i]);
		memset(f,0x3f3f3f3f,sizeof(f));
		f[0] = 0;
		for (int i = 0; i < n; i++)
			for (int j = cost[i]; j <= m; j++)
				if (f[j-cost[i]] != 0x3f3f3f3f)
					f[j] = min(f[j],f[j-cost[i]]+w[i]);
		if (f[m] == 0x3f3f3f3f)
			printf("This is impossible.\n");
		else printf("The minimum amount of money in the piggy-bank is %d.\n",f[m]);
	}
}