HDU 2159 FATE — 二維完全背包問題解析

問題背景

給定忍耐度 m、需殺怪獸數 s、目標經驗值 n，以及 k 種怪獸，每種有經驗值 a[i] 和消耗忍耐度 b[i]。怪獸可重複擊殺（完全背包）。求在忍耐度不超過 m、擊殺怪獸數不超過 s 的前提下，能否獲得至少 n 經驗值；若不能，輸出剩餘忍耐度的最大值。

狀態定義與轉移

dp[j][p]：消耗忍耐度 j、擊殺 p 隻怪獸可獲得的最大經驗值。

轉移方程：

dp[j][p] = max(dp[j][p], dp[j - b[i]][p - 1] + a[i])

其中 j 從 b[i] 遞增到 m（完全背包特性），p 從 1 到 s。

參考代碼 (C++)

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

int dp[110][110];
int a[110], b[110];
int n, m, k, s;

int main() {
    while (scanf("%d%d%d%d", &n, &m, &k, &s) != EOF) {
        for (int i = 0; i < k; ++i) cin >> a[i] >> b[i];
        memset(dp, 0, sizeof(dp));

        for (int i = 0; i < k; ++i) {
            for (int j = b[i]; j <= m; ++j) {        // 完全背包：正序枚舉容量
                for (int p = 1; p <= s; ++p) {       // 枚舉擊殺數量
                    dp[j][p] = max(dp[j][p], dp[j - b[i]][p - 1] + a[i]);
                }
            }
        }

        int cnt = 0;
        for (int j = 0; j <= m; ++j) {
            if (dp[j][s] < n) ++cnt;  // 經驗值不足 n 的忍耐度值計數
        }
        printf("%d\n", m - cnt);       // 輸出最大剩餘忍耐度
    }
    return 0;
}

關鍵點解析

• 二維代價：忍耐度與擊殺數量雙重限制，構成二維 DP。
• 完全背包：怪獸可重複選擇，內層循環 j 正序枚舉。
• 答案提取：統計 dp[j][s] < n 的 j 個數，用 m - cnt 得到最大剩餘忍耐度。

複雜度

• 時間：O(k × m × s)，m, s ≤ 100，極快。
• 空間：O(m × s)。