HDU 2159 Fate - 二維背包問題解法

題目大意

有 k 種物品，每種有體積 c[i]、價值 w[i]。背包容量 V，必須恰好裝 s 件物品。求最大價值是否 ≥ n，若否輸出 -1，否則輸出「剩餘容量最大值」(即 V - 最小達標體積)。

動態規劃模型

dp[i][j]：體積為 i、選 j 件物品的最大價值

• 初始：dp[0][0] = 0，其餘 -∞
• 轉移：dp[i][p] = max(dp[i][p], dp[i-c[j]][p-1] + w[j])
• 完全背包式枚舉：外層體積，中層物品，內層件數

代碼實現

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

int n, V, k, s;
int dp[110][110], w[110], c[110];

int main() {
    while (~scanf("%d%d%d%d", &n, &V, &k, &s)) {
        for (int i = 1; i <= k; i++) scanf("%d%d", &w[i], &c[i]);
        memset(dp, 0, sizeof(dp));
        
        for (int i = 1; i <= V; i++)       // 體積
            for (int j = 1; j <= k; j++)   // 物品種類
                for (int p = 1; p <= s; p++) // 件數
                    if (i >= c[j])
                        dp[i][p] = max(dp[i][p], dp[i-c[j]][p-1] + w[j]);
        
        if (dp[V][s] < n) {
            puts("-1");
        } else {
            for (int i = V-1; i >= 0; i--)
                if (dp[i][s] < n) { printf("%d\n", V-i-1); break; }
        }
    }
    return 0;
}

關鍵點

1. 三維狀態壓縮為二維：體積 × 件數，物品種類在中層迭代實現無限件
2. 輸出邏輯：找最小體積 i 使 dp[i][s] ≥ n，答案為 V - i - 1 (剩餘容量)
3. 數組大小 110×110 足夠覆蓋約束