https://acm.hdu.edu.cn/showproblem.php?pid=1114
完全背包
/***************************
# 2013-11-22 13:20:22
# Time: MS Memory: K
# Author: zyh
***************************/
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
const int INF = 99999999;
int n,f[10005],c[505],w[505];
int completepack(int V)
{
int i,v;
for(f[0]=0,i=1;i<=V;i++) f[i]=INF;
for(i=0;i<n;i++){
for(v=c[i];v<=V;v++){
if(f[v]>f[v-c[i]] +w[i] )
f[v] = f[v-c[i]]+w[i];
}
}
return f[V];
}
int main()
{
int t,i,a,b,ans,flag;
scanf("%d",&t);
while(t--){
scanf("%d%d",&a,&b);
b = b - a;
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%d%d",&w[i],&c[i]);
ans = completepack(b);
if(ans==INF) puts("This is impossible.");
else printf("The minimum amount of money in the piggy-bank is %d.\n",ans);
}
return 0;
}