HDU 1248 寒冰王座：完全背包問題的經典應用

題目故事與數學模型

HDU 1248《寒冰王座》將完全背包問題包裝在死亡騎士購買藥水的情境中：手持面值 N 元鈔票（N ≤ 10,000），商店販售三種道具——血瓶 150 元、魔法藥 200 元、無敵藥水 350 元，不找零，多餘金額視為小費。目標是找出最小小費，即最大化花費金額不超過 N。

這是標準的完全背包：物品無限供給，體積即價格，價值同體積，求容量 N 下的最大價值，答案為 N - dp[N]。

動態規劃狀態定義與轉移

• dp[j]：花費不超過 j 元時的最大實際花費金額
• 初始化：dp[0..N] = 0
• 轉移方程：對每種物品價格 cost，對 j = cost .. N 執行 dp[j] = max(dp[j], dp[j-cost] + cost)

空間優化的一維陣列寫法

int dp[10005];
int cost[3] = {150, 200, 350};

for (int i = 0; i < 3; ++i) {
    for (int j = cost[i]; j <= N; ++j) {
        dp[j] = max(dp[j], dp[j - cost[i]] + cost[i]);
    }
}
printf("%d\n", N - dp[N]);

關鍵細節與優化技巧

1. 只需三種物品：外層迴圈固定 3 次，內層最多 10,000 次，總操作約 30,000 次，極快。
2. 多測資處理：每組測資前必須 memset(dp, 0, sizeof(dp)) 重置。
3. 答案計算：N - dp[N] 即為最小小費，樣例 N=900 可湊齊 900（150×6 或 200×3+150×2 等），小費 0；N=250 最大花費 200，小費 50。

完整 AC 程式碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int dp[10005];
int cost[3] = {150, 200, 350};

int main() {
    int T, N;
    scanf("%d", &T);
    while (T--) {
        memset(dp, 0, sizeof(dp));
        scanf("%d", &N);
        for (int i = 0; i < 3; ++i) {
            for (int j = cost[i]; j <= N; ++j) {
                dp[j] = max(dp[j], dp[j - cost[i]] + cost[i]);
            }
        }
        printf("%d\n", N - dp[N]);
    }
    return 0;
}

延伸思考：完全背包的通用模板

若物品數量變多（如 M 種），相同邏輯適用。若需輸出具體購買方案，可額外維護 pre[j] 記錄最後加入的物品索引，反向追蹤即可。本題因物品極少、價值等於體積，是完全背包最精簡的教學案例。