題意：題目的意思是有一個儲蓄罐，裡面放了硬幣，只知道儲蓄罐裝了硬幣和沒裝硬幣時的重量，並且知道每種面值硬幣的重量。現在要求儲蓄罐中可能的最小金額。若儲蓄罐中硬幣的重量和每種面值硬幣的重量不能匹配，則輸出impossible。
分析：這又是一道典型的完全背包問題，因為我們可以認為儲蓄罐中每種面值的錢幣是任意多的。這道題只是把求最大值改為了求最小值。並且背包要求完全裝滿。這個時候要注意初始化的時候不能初始為負無窮而應該是正無窮了。但是我們不能這麼定義：
[cpp]
#define MAX_INT 0x7fffffff
#define MAX_INT 0x7fffffff
因為若是這麼定義在計算F[v-cost]+weight時F[]會溢出，因為是做加法，這一點應該特別注意。我們應該定義MAX_INT為F[]可能的最大值。F[]的含義是前i件物品恰放入一個容量為v的背包可以獲得的最小價值。現在v的最大值是10000，錢幣的最輕重量是1，就是說最多可能有10000個錢幣，錢幣的最大面值是50000，也就是說，F[]的最大值是500000000。所以我們應該
[cpp]
#define MAX_INT 500000000
#define MAX_INT 500000000
見代碼：
[cpp]
#include <iostream>
using namespace std;
#define MAX_INT 50000000
int F[10001];
int P[501];
int W[501];
int min(int a, int b)
{
return a<b?a:b;
}
void CompletePack(int cost, int weight, int V)
{
for (int v=cost; v<=V; ++v) {
F[v] = min(F[v], F[v-cost]+weight);
}
}
int main(int argc, char **argv)
{
int T, a, b, V, n;
cin>>T;
while (T--) {
cin>>a>>b;
V = b - a;
cin>>n;
F[0] = 0;
for (int i=1; i<=10000; ++i)
F[i] = MAX_INT;
for (int i=1; i<=n; ++i) {
cin>>P[i]>>W[i];
CompletePack(W[i], P[i], V);
}
if (F[V]==MAX_INT)
cout<<"This is impossible."<<endl;
else
cout<<"The minimum amount of money in the piggy-bank is "<<F[V]<<"."<<endl;
}
system("pause");
return 0;
}
#include <iostream>
using namespace std;
#define MAX_INT 50000000
int F[10001];
int P[501];
int W[501];
int min(int a, int b)
{
return a<b?a:b;
}
void CompletePack(int cost, int weight, int V)
{
for (int v=cost; v<=V; ++v) {
F[v] = min(F[v], F[v-cost]+weight);
}
}
int main(int argc, char **argv)
{
int T, a, b, V, n;
cin>>T;
while (T--) {
cin>>a>>b;
V = b - a;
cin>>n;
F[0] = 0;
for (int i=1; i<=10000; ++i)
F[i] = MAX_INT;
for (int i=1; i<=n; ++i) {
cin>>P[i]>>W[i];
CompletePack(W[i], P[i], V);
}
if (F[V]==MAX_INT)
cout<<"This is impossible."<<endl;
else
cout<<"The minimum amount of money in the piggy-bank is "<<F[V]<<"."<<endl;
}
system("pause");
return 0;
}
