1 /*
 2 Author:    Leo.W
 3 Descriptipn:    一個(gè)多重背包的問題，給定儲(chǔ)物罐的容納量W，和提供的不同種類錢幣的價(jià)值與質(zhì)量來估算罐中錢幣的最小價(jià)值
 4 How to Do:    兩層for循環(huán)，DP[j]=max{DP[j-w[i]*k]+v[i]*k}(k<j/w[i]);初始化時(shí)需注意的是DP[0]初值為零,數(shù)組其他均為負(fù)無窮。
 5   */
 6 #include <stdio.h>
 7 #include <iostream>
 8 #include <string.h>
 9 using namespace std;
10 #define MAXSIZE 10000
11 #define wupin 500
12 #define MINS -0x7fffffff-1
13 int DP[MAXSIZE];
14 int w[wupin];
15 int v[wupin];
16 int main(){
17     //freopen("in.txt","r",stdin);
18     int i,j,t;
19     scanf("%d",&t);
20     while (t--){
21         int wa,wb;
22         scanf("%d%d",&wb,&wa);
23         int weight=wa-wb;
24         for(i=0;i<=weight;i++)
25             DP[i]=MINS;
26         DP[0]=0;
27         int moneyKinds;
28         scanf("%d",&moneyKinds);
29         for(i=0;i<moneyKinds;i++)
30             scanf("%d%d",&v[i],&w[i]);
31         for(i=0;i<moneyKinds;i++){            
32             for(j=w[i];j<=weight;j++){//此處是關(guān)鍵
33                 if((DP[j]>DP[j-w[i]]+v[i]&&DP[j-w[i]]+v[i]>0)||DP[j]<0)
34                     DP[j]=DP[j-w[i]]+v[i];
35             }
36         }
37         if(DP[weight]>0)
38             printf("The minimum amount of money in the piggy-bank is %d.\n",DP[weight]);
39         else
40             printf("This is impossible.\n");
41 
42     }
43     return 0;
44 } 
45