HDU 2602 Bone Collector 01背包經典入門

問題描述

有 N 塊骨頭（N ≤ 1000），每塊有價值 v_i 和體積 w_i。背包容量 V ≤ 1000。求最大總價值。

01 背包 DP

狀態：dp[j] = 容量為 j 時的最大價值。
轉移：對每個物品，從大到小枚舉容量：
dp[j] = max(dp[j], dp[j - w[i]] + v[i])

代碼實現

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

關鍵點

• 逆序枚舉容量保證每個物品只用一次（01背包核心）
• 空間優化至一維數組
• 數據範圍小（N,V ≤ 1000），O(NV) = 10⁶ 極快
• 答案 < 2³¹，int 足夠

變體擴展

若求方案數、或輸出具體選取物品，需額外記錄路徑或計數數組。