HDU 2602 0-1背包問題：動態規劃C++解法詳解

HDU 2602 Bone Collector - 0-1背包問題完整解析

經典0-1背包問題：給定N件物品，每件有價值和體積，背包容量V，求裝入物品的最大總價值。每件物品只能選或不選(0-1特性)。本文提供C++動態規劃解法，含狀態定義、轉移方程、空間優化及完整AC代碼。

問題描述

• 測試用例T組
• 每組：N件物品(≤1000)，背包容量V(≤1000)
• 輸入：N個價值值，N個體積值
• 輸出：最大總價值(<2^31)

動態規劃核心邏輯

狀態定義：dp[i][j]表示前i件物品裝入容量j背包的最大價值

轉移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - vol[i]] + val[i])  // j >= vol[i]
dp[i][j] = dp[i-1][j]                                       // j < vol[i]

• dp[i-1][j]：不選第i件
• dp[i-1][j-vol[i]] + val[i]：選第i件(前提容量夠)

初始條件：dp[0][j] = 0(0件物品價值為0)

二維DP完整代碼

int dp[MAXN] = {0}; // 一維數組

for (int i = 1; i <= N; i++) {
    for (int j = V; j >= vol[i]; j--) { // 逆序！關鍵
        dp[j] = max(dp[j], dp[j - vol[i]] + val[i]);
    }
}

逆序原因：正序會導致dp[j-vol[i]]已被當前輪更新，實際上使用了同一物品多次(變成完全背包)。逆序保證讀取的是上一輪狀態。

優化版完整代碼

版本時間複雜度空間複雜度適用場景
二維DPO(N×V)O(N×V)需要路徑回溯、教學演示
一維DPO(N×V)O(V)僅需最優值、大規模數據、競賽標準


測試樣例
輸入:
1
5 10
1 2 3 4 5
5 4 3 2 1

輸出:
14

解析:
物品: (價值,體積) = (1,5) (2,4) (3,3) (4,2) (5,1)
最優選擇: 選擇物品3,4,5 → 體積3+2+1=6 ≤ 10，價值3+4+5=12
更優: 選擇物品2,3,4,5 → 體積4+3+2+1=10，價值2+3+4+5=14 ✓


常見錯誤與避坑

一維DP正序循環：會轉化為完全背包，答案偏大
數組大小不足：N,V≤1000，開[1001]或[1005]安全
多測試用例未重置：每組案例前memset(dp, 0, ...)
輸入讀取混淆：先讀N個價值，再讀N個體積，不要交叉讀取
長整型溢出：題目說明答案<2^31，int足夠，但習慯用long long更安全


進階擴展：輸出具體選擇方案

背包問題家族對比

類型
物品可選次數
內層循環方向
核心區別
0-1背包
0或1次
逆序(j=V..vol)
每件唯一
完全背包
無限次
正序(j=vol..V)
可重複選
多重背包
有限次數
二進制拆分/單調隊列
數量受限
分組背包
組內互斥選1
逆序+組內遍歷
分組約束


0-1背包是動態規劃入門的經典模型，掌握其「狀態定義→轉移方程→初始化→序優化」完整思維流程，是解決所有背包變體問題的基石。HDU 2602作為模板題，建議熟練掌握一維逆序優化寫法，並能手寫二維版本用於路徑回溯場景。