HDU 2602 Bone Collector：經典 0/1 背包問題完整解析與代碼實現

HDU 2602 Bone Collector：經典 0/1 背包問題完整解析

在算法競賽與動態規劃的學習歷程中，HDU 2602 Bone Collector 是一道極具代表性的入門級 0/1 背包問題。題目背景設定為「骨頭收集者」泰迪，他擁有一個容量為 V 的背包，沿途有 N 塊骨頭，每塊骨頭具有各自的價值 w[i] 與體積 c[i]。目標是在不超過背包容量的前提下，選取骨頭使總價值最大化。這正是標準的 0/1 背包模型：每件物品只能選或不選，不可分割、不可重複。

核心思路：一維 DP 滾動數組優化

狀態定義：dp[j] 表示容量為 j 的背包所能裝載的最大價值。
狀態轉移方程：dp[j] = max(dp[j], dp[j - c[i]] + w[i])，其中 j 從 V 遞減至 c[i]，保證每件物品僅被使用一次。
初始條件：dp[0..V] = 0。
最終答案：dp[V]。

時間複雜度 O(N·V)，空間複雜度 O(V)，滿足題目限制 N, V ≤ 1000。

參考代碼（C++）

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

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, V; scanf("%d%d", &N, &V);
        int w[1005], c[1005];
        for (int i = 0; i < N; ++i) scanf("%d", &w[i]);
        for (int i = 0; i < N; ++i) scanf("%d", &c[i]);
        int dp[1005] = {0};
        for (int i = 0; i < N; ++i) {
            for (int j = V; j >= c[i]; --j) {
                dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
            }
        }
        printf("%d\n", dp[V]);
    }
    return 0;
}

關鍵點總結

• 內層循環必須逆序，否則會退化為完全背包（可重複選取）。
• 數據範圍較小，int 足夠（題目保證答案 < 2³¹）。
• 多測試用例處理：每個 case 獨立初始化 dp 數組。

掌握此題，即掌握 0/1 背包的核心範式，為後續學習完全背包、多重背包、分組背包等變體打下堅實基礎。