题意：完全背包的变形
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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]);
}
}HDU - 1114 Piggy-Bank,布布扣,bubuko.com
原文：http://blog.csdn.net/u011345136/article/details/20914309