HDOJ 2159 FATE 二維背包問題：經驗與忍耐雙約束動態規劃完整解析

問題描述

需要達到經驗值 n，初始忍耐度 m。有 k 種怪物，第 i 種給經驗 a[i]、消耗忍耐 b[i]。最多打 s 隻怪。求剩餘忍耐度最大值（即總消耗最小），無法達標輸出 -1。

模型轉化：二維費用 01 背包

• 物品：每種怪物可打多次，但總數 ≤ s → 展開為多個 01 物品或用「件數」作第三維
• 費用 1：忍耐度消耗 b[i]，容量 m
• 費用 2：打怪數量（每隻佔 1），容量 s
• 價值：經驗值 a[i]
• 目標：在雙重容量約束下，經驗值 ≥ n，且忍耐消耗最小

狀態定義與轉移

dp[j][l]：消耗忍耐 j、打怪 l 隻時的最大經驗值。

轉移方程（完全背包正序，因同種怪可重複打）：

for i = 0..k-1:
    for j = b[i]..m:          // 忍耐度正序
        for l = 1..s:         // 打怪數正序
            dp[j][l] = max(dp[j][l], dp[j-b[i]][l-1] + a[i])

完整代碼實現

#include <stdio.h>
#include <string.h>

int main() {
    int n, m, k, s;
    int a[102], b[102];
    int dp[102][102];  // m, s ≤ 100
    
    while (scanf("%d %d %d %d", &n, &m, &k, &s) != EOF) {
        for (int i = 0; i < k; i++)
            scanf("%d %d", &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 l = 1; l <= s; l++) {
                    dp[j][l] = max(dp[j][l], dp[j - b[i]][l - 1] + a[i]);
                }
            }
        }
        
        // 尋找答案：經驗 ≥ n 且忍耐消耗最小（剩餘最大）
        int ans = -1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= s; j++) {
                if (dp[i][j] >= n) {
                    ans = m - i;  // 剩餘忍耐
                    break;
                }
            }
            if (ans != -1) break;
        }
        
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點解析

1. 二維數組足夠：利用「件數」作為第二維費用，避免三維數組
2. 完全背包正序：同種怪可重複打，j 和 l 均正序遍歷
3. 狀態含義清晰：dp 存最大經驗，而非可行性，便於 ≥ n 判斷
4. 答案檢索策略：按忍耐消耗從小到大遍歷，首個滿足經驗要求者即最優

複雜度分析

• 時間：O(k × m × s) ≤ 100 × 100 × 100 = 10⁶，極快
• 空間：O(m × s) = 10⁴

二維背包通用模板總結

// 01 背包：逆序
for i: for v=V..cost1: for u=U..cost2: dp[v][u]=max(dp[v][u], dp[v-c1][u-c2]+w)

// 完全背包：正序
for i: for v=cost1..V: for u=cost2..U: dp[v][u]=max(dp[v][u], dp[v-c1][u-c2]+w)

// 多重背包：二進制拆分轉 01，或用 used 數組法