HDU 1114 Piggy-Bank：完全背包求最小金額

題目大意

豬儲錢罐空重 E、滿重 F，硬幣 N 種，每種有面值 P 和重量 W。求總重量恰好為 F-E 時的最小面值總和。不可行輸出 This is impossible.。

完全背包 DP

• dp[w]：重量恰好為 w 的最小面值。初始 dp[0]=0，其余 INF。
• 狀態轉移：對每種硬幣，for w=W..V: dp[w] = min(dp[w], dp[w-W]+P)。
• 答案 dp[V] (V=F-E)，若仍為 INF 則不可能。

代碼實現

#include <iostream>
#include <cstring>
#define MAXV 10005
#define INF 0x3f3f3f3f
int dp[MAXV];
int main() {
    int T; cin >> T;
    while (T--) {
        int E, F, N; cin >> E >> F >> N;
        int V = F - E;
        fill(dp, dp+V+1, INF); dp[0] = 0;
        for (int i=0; i> P >> W;
            for (int w=W; w<=V; w++)
                if (dp[w-W] != INF) dp[w] = min(dp[w], dp[w-W]+P);
        }
        if (dp[V] == INF) cout << "This is impossible." << endl;
        else cout << "The minimum amount of money in the piggy-bank is " << dp[V] << "." << endl;
    }
    return 0;
}

關鍵點

• 完全背包：內層循環 w 從小到大（可重複使用）。
• V ≤ 10000，N ≤ 500，O(NV) = 5×10⁶ 極快。
• 輸出格式嚴格匹配樣例（句號、大小寫）。