【DP|完全背包】HDU-1114 Piggy-Bank

Piggy-Bank

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid. 

But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs! 

Input The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W is it's weight in grams. 

Output Print exactly one line of output for each test case. The line must contain the sentence "The minimum amount of money in the piggy-bank is X." where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line "This is impossible.". 

Sample Input

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
        

Sample Output

The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
        

Source Central Europe 1999    

————————————————————開森的分割線———————————————————— 思路：這是背包九講裡的第二講。完全背包。對于完全背包來說，不再是每樣物品隻有一個，是以我們不必保證“前一個狀态的f[ ]值”不會被覆寫，即不必逆序枚舉背包容量了。還記得為什麼需要逆序枚舉嗎？ 回憶：再看01背包的狀态轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}; 當我們計算f[i][v]的時候，需要用到f[i-1][v]和f[i-1][v-c[i]]的值，而省略次元[i]之後逆序枚舉可以保證f[v-c[i]]的值是在i - 1時計算出來的而不是在 i 的時候計算的。顯然，省去次元[i]之後，正序枚舉會覆寫掉f[v-c[i]]的值。 也就是說：如果這次我用到的f[v-c[i]]是前i - 1個物品計算得到的，是存在的，才能DP得到這次的f[v]。換句話說，對于 i 這件物品，我隻有兩種選擇，能選or不能選。不能選：因為f[i-1][v]比f[i-1][v-c[i]]+w[i]的價值更大，選了f[i][v] = f[i-1][v-c[i]]+w[i]（v狀态價值更小）就是缺心眼。能選：放進了 i ，v狀态價值增大。 回到完全背包。 這次的狀态轉移是這樣的：

for i=1..N
   for v=0..V
        f[v]=max{f[v],f[v-c[i]]+w[i]};
           

未壓縮次元之前是這樣的：f[i][v] = max{f[i−1][v], f[i−1][v−c[i]]+w[i], f[i−1][v−c[i]*2]+w[i]*2,f[i−1][v−c[i]*3]+w[i]*3, ......f[i−1][v−v]+w[i]*v} DP的過程是這樣的：對之前的v(0..V)狀态，我放一個 i，再放一個 i，再放一個 i ……看看放幾個 i 價值最大。 此外，本題還有一點：要求的不是價值最大，而是價值最小。這就是初始化的技巧了。首先f[0] = 0，這意味着每一次都是從背包為空開始，這一點是一定能達到的。其次，所有點初始化為SUP(無窮大)，表示無法到達。一旦可以到達，那肯定是比SUP小的啦。 代碼如下：

/****************************************/
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <algorithm>
 #include <cmath>
 #include <stack>
 #include <queue>
 #include <vector>
 #include <map>
 #include <string>
 #include <iostream>
 using namespace std;
/****************************************/
const int MAXN = 510, N = 10010;
const int SUP = 0x7F7F7F7F;
int worth[MAXN], f[N];

int main()
{
	int cas;
	scanf("%d", &cas);
	while(cas--) {
		int n, E, F;
		scanf("%d%d%d", &E, &F, &n);
		int V = F - E, cost;
		memset(f, 0x7F, sizeof(f));
		f[0] = 0;
		for(int i = 0; i < n; i++) {
			scanf("%d%d", &worth[i], &cost);
			for(int j = cost; j <= V; j++)
				if(f[j-cost]+worth[i] < f[j])
					f[j] = f[j-cost] + worth[i];
		}
		if(f[V] == SUP)
			printf("This is impossible.\n");
		else
			printf("The minimum amount of money in the piggy-bank is %d.\n", f[V]);
	}
	return 0;
}