HDU 2159 FATE：二維費用完全背包詳解

HDU 2159 FATE：二維費用完全背包詳解

經典背包變體：主角需在 忍耐度 m 與 殺怪上限 s 兩重約束下，通過擊殺怪物（無限供給）獲取經驗值，目標是達到 經驗值 n 並最大化剩餘忍耐度。若無法達標輸出 -1。

問題建模

• 物品：k 種怪物，第 i 種提供經驗 w[i]、消耗忍耐 c[i]，數量無限。
• 背包容量：兩維 —— 忍耐度上限 m（成本）、殺怪數上限 s（件數）。
• 目標：在 dp[j][l] 表示「殺 j 隻怪、消耗忍耐 l 可獲最大經驗」的意義下，找最小 l 使 dp[j][l] ≥ n，答案為 m - l。

狀態轉移方程

完全背包順序遍歷：

for i = 1..k:           // 遍歷物品（怪物）
  for j = 1..s:         // 遍歷件數（殺怪數）
    for l = c[i]..m:    // 遍歷忍耐度（成本）
      dp[j][l] = max(dp[j][l], dp[j-1][l-c[i]] + w[i]);

關鍵點：j 從 1 遞增至 s，l 從 c[i] 遞增至 m —— 這正是完全背包（可重複選擇同一物品）的標準寫法。

答案提取

int ans = INF;
for (int i = 1; i <= k; ++i)
  for (int j = 1; j <= s; ++j)
    for (int l = guaiwu[i].c; l <= m; ++l)
      if (dp[j][l] >= n) ans = min(ans, l);

if (dp[s][m] < n) puts("-1");
else printf("%d\n", m - ans);

完整 AC 代碼

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

const int INF = 0x3f3f3f3f;
int dp[110][110];
struct Monster { int exp, pat; } a[110];

int main() {
    int n, m, k, s;
    while (~scanf("%d%d%d%d", &n, &m, &k, &s)) {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= k; ++i) scanf("%d%d", &a[i].exp, &a[i].pat);
        for (int i = 1; i <= k; ++i)
            for (int j = 1; j <= s; ++j)
                for (int l = a[i].pat; l <= m; ++l)
                    dp[j][l] = max(dp[j][l], dp[j-1][l-a[i].pat] + a[i].exp);
        int ans = INF;
        for (int j = 1; j <= s; ++j)
            for (int l = 0; l <= m; ++l)
                if (dp[j][l] >= n) ans = min(ans, l);
        if (ans == INF) puts("-1");
        else printf("%d\n", m - ans);
    }
    return 0;
}

複雜度分析

• 時間：O(k * s * m)，k,s,m ≤ 100 → 約 10⁶ 操作，極輕鬆。
• 空間：O(s * m)，110×110 整型陣列。

易錯點提醒

1. 循環順序：j、l 必須正向遍歷（完全背包），反向則變成 01 背包。
2. 初始化：dp 全 0 即可，dp[0][*] = 0 表示殺 0 隻怪經驗為 0。
3. 答案定義：輸出「剩餘忍耐度」m - 最小消耗，而非消耗本身。

總結

HDU 2159 是「二維費用完全背包」的標準模板題：件數 + 成本雙重約束、無限物品、最大化價值再反推最小成本。掌握循環順序與狀態定義，同類問題（如 HDU 2639、POJ 1014 變體）皆可速解。