【題目敘述】https://vjudge.net/problem/HDU-1114
【解題想法】DP 0-1 Knapsack
- 小豬撲滿容納的硬幣重量 = F – E
- 每個硬幣的重量和價值分別是W[i]和P[i]。
- dp[i]：當小豬撲滿容納的硬幣重量為 i 時的「最小」價值。初始值設為INF，但 dp[0] = 0。
- 循序檢驗每一枚硬幣的{W[i], P[i]}，更新dp[i]。
- 狀態轉移方程：
- 當小豬撲滿容納的硬幣重量為 j 時，
- 取第 i 枚硬幣：價值為 dp[j – W[i]] + P[i]
- 不取第 i 枚硬幣：價值為原來的 dp[j]
- dp[j] = min(dp[j], dp[j – W[i]] + P[i]);
#include <iostream>
#include <cstring>
using namespace std;
#define INF 1e9
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int T, E, F, N;
cin >> T;
while (T--){
cin >> E >> F;
cin >> N;
int P[N], W[N];
for (int i=0; i<N; i++){
cin >> P[i] >> W[i];
}
int dp[F - E + 1];
for (int i=0; i<=F-E; i++){
dp[i] = INF;
}
dp[0] = 0;
for (int i=0; i<N; i++){
for (int j=W[i]; j<=F-E; j++){
dp[j] = min(dp[j], dp[j - W[i]] + P[i]);
}
}
if (dp[F - E] == INF){
cout << "This is impossible.\n";
} else {
cout << "The minimum amount of money in the piggy-bank is "
<< dp[F - E] << ".\n";
}
}
return 0;
}