knapsack.cpp

// knapsack.cpp
// -----------------------------------------------------------------
// 0/1 Knapsack：
//   1. 二維 DP O(nW) + 回溯還原選了哪些物品
//   2. 一維空間優化 DP O(W)
//   3. 分支限界（回溯 + 分數背包上界剪枝）
//
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o knapsack knapsack.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
#include <chrono>

using namespace std;

struct Item { int w, v; };

// ---------- 1. 二維 DP + 還原方案 ----------
pair<int, vector<int>> knapsackDP2D(const vector<Item>& items, int W) {
    int n = (int)items.size();
    // dp[i][c] = 只考慮前 i 件、容量 c 的最大價值
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int c = 0; c <= W; ++c) {
            dp[i][c] = dp[i - 1][c];                       // 不拿第 i 件
            if (c >= items[i - 1].w)                       // 拿第 i 件
                dp[i][c] = max(dp[i][c],
                               dp[i - 1][c - items[i - 1].w] + items[i - 1].v);
        }
    // 回溯：從 dp[n][W] 反推每件拿或不拿
    vector<int> chosen;
    int c = W;
    for (int i = n; i >= 1; --i)
        if (dp[i][c] != dp[i - 1][c]) {                    // 值變了 -> 有拿
            chosen.push_back(i - 1);
            c -= items[i - 1].w;
        }
    reverse(chosen.begin(), chosen.end());
    return {dp[n][W], chosen};
}

// ---------- 2. 一維空間優化（容量倒著掃） ----------
int knapsackDP1D(const vector<Item>& items, int W) {
    vector<int> dp(W + 1, 0);
    for (const auto& it : items)
        for (int c = W; c >= it.w; --c)                    // 倒序避免重複拿
            dp[c] = max(dp[c], dp[c - it.w] + it.v);
    return dp[W];
}

// ---------- 3. 分支限界 ----------
// 上界：剩餘容量用「分數背包」鬆弛（物品可切割）——一定 >= 真實最佳
class BranchAndBound {
    vector<Item> items;                  // 依價值密度排序後
    int W, best = 0;
public:
    long long nodes = 0;

    int solve(vector<Item> its, int W_) {
        items = std::move(its);
        W = W_;
        sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
            return (long long)a.v * b.w > (long long)b.v * a.w;  // 密度遞減
        });
        best = 0; nodes = 0;
        dfs(0, 0, 0);
        return best;
    }
private:
    double fractionalBound(int idx, int cap) {
        double bound = 0;
        for (int i = idx; i < (int)items.size() && cap > 0; ++i) {
            if (items[i].w <= cap) { bound += items[i].v; cap -= items[i].w; }
            else { bound += (double)items[i].v * cap / items[i].w; cap = 0; }
        }
        return bound;
    }
    void dfs(int idx, int usedW, int val) {
        ++nodes;
        best = max(best, val);
        if (idx == (int)items.size()) return;
        // 剪枝：目前價值 + 樂觀上界 <= 已知最佳 -> 整枝砍掉
        if (val + fractionalBound(idx, W - usedW) <= best) return;
        if (usedW + items[idx].w <= W)                     // 拿
            dfs(idx + 1, usedW + items[idx].w, val + items[idx].v);
        dfs(idx + 1, usedW, val);                          // 不拿
    }
};

int main() {
    // ---- 範例 1：經典小例 ----
    cout << "=== Example 1: classic 3-item case ===\n";
    vector<Item> a = {{10, 60}, {20, 100}, {30, 120}};
    auto [bestA, pickA] = knapsackDP2D(a, 50);
    cout << "W=50, items (w,v) = (10,60)(20,100)(30,120)\n";
    cout << "best value = " << bestA << " (expect 220)\n";
    cout << "chosen items:";
    for (int i : pickA)
        cout << " #" << i << "(w=" << a[i].w << ",v=" << a[i].v << ")";
    cout << "\n1D DP check = " << knapsackDP1D(a, 50) << "\n\n";

    // ---- 範例 2：手算教學例（6 件） ----
    cout << "=== Example 2: 6-item worked example ===\n";
    vector<Item> b = {{2,3},{3,4},{4,5},{5,8},{9,10},{1,1}};
    auto [bestB, pickB] = knapsackDP2D(b, 10);
    cout << "W=10 -> best = " << bestB << ", chosen:";
    for (int i : pickB) cout << " #" << i;
    int wSum = 0, vSum = 0;
    for (int i : pickB) { wSum += b[i].w; vSum += b[i].v; }
    cout << "  (total w=" << wSum << ", v=" << vSum << ")\n\n";

    // ---- 範例 3：DP vs 分支限界，隨機大例 ----
    cout << "=== Example 3: DP vs branch-and-bound (n=30, W=500) ===\n";
    mt19937 rng(42);
    uniform_int_distribution<int> wd(5, 60), vd(10, 100);
    vector<Item> c;
    for (int i = 0; i < 30; ++i) c.push_back({wd(rng), vd(rng)});
    int W = 500;

    auto t0 = chrono::steady_clock::now();
    int dpBest = knapsackDP1D(c, W);
    auto t1 = chrono::steady_clock::now();
    BranchAndBound bb;
    int bbBest = bb.solve(c, W);
    auto t2 = chrono::steady_clock::now();
    cout << "DP  : best=" << dpBest << "  ("
         << chrono::duration<double, milli>(t1 - t0).count() << " ms)\n";
    cout << "B&B : best=" << bbBest << "  ("
         << chrono::duration<double, milli>(t2 - t1).count()
         << " ms, nodes=" << bb.nodes << ")\n";
    cout << "agree = " << (dpBest == bbBest ? "yes" : "NO!") << "\n\n";

    // ---- 範例 4：為什麼叫「偽多項式」——W 變大 DP 就爆 ----
    cout << "=== Example 4: pseudo-polynomial blow-up ===\n";
    for (int bigW : {1000, 100000, 10000000}) {
        auto t3 = chrono::steady_clock::now();
        int r = knapsackDP1D(c, bigW);
        auto t4 = chrono::steady_clock::now();
        cout << "W=" << bigW << " -> best=" << r << "  ("
             << chrono::duration<double, milli>(t4 - t3).count() << " ms)\n";
    }
    cout << "(n fixed at 30; time grows linearly with W, the VALUE)\n";
    return 0;
}