bin_packing.cpp

// bin_packing.cpp
// -----------------------------------------------------------------
// Bin Packing（裝箱問題）：
//   1. Next Fit (NF)：只看最後一個箱子，2-近似
//   2. First Fit (FF)：掃描全部箱子放第一個裝得下的，~1.7 OPT
//   3. First Fit Decreasing (FFD)：先由大到小排序再 FF，<= 11/9 OPT + 6/9
//   4. 下界：ceil(總和 / 容量)，以及精確解（小實例枚舉）
//
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o bin_packing bin_packing.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>

using namespace std;

struct Packing {
    vector<vector<int>> bins;    // 每箱裝的「物品重量」清單
    int count() const { return (int)bins.size(); }
};

// ---------- 1. Next Fit ----------
Packing nextFit(const vector<int>& items, int cap) {
    Packing p;
    int space = -1;
    for (int w : items) {
        if (space < w) {                    // 開新箱（舊箱永久封箱）
            p.bins.push_back({});
            space = cap;
        }
        p.bins.back().push_back(w);
        space -= w;
    }
    return p;
}

// ---------- 2. First Fit ----------
Packing firstFit(const vector<int>& items, int cap) {
    Packing p;
    vector<int> space;                      // 每箱剩餘空間
    for (int w : items) {
        int placed = -1;
        for (int b = 0; b < (int)space.size(); ++b)
            if (space[b] >= w) { placed = b; break; }
        if (placed == -1) {
            p.bins.push_back({});
            space.push_back(cap);
            placed = (int)space.size() - 1;
        }
        p.bins[placed].push_back(w);
        space[placed] -= w;
    }
    return p;
}

// ---------- 3. First Fit Decreasing ----------
Packing firstFitDecreasing(vector<int> items, int cap) {
    sort(items.begin(), items.end(), greater<int>());
    return firstFit(items, cap);
}

// ---------- 4a. 下界 ----------
int lowerBound(const vector<int>& items, int cap) {
    int total = accumulate(items.begin(), items.end(), 0);
    return (total + cap - 1) / cap;
}

// ---------- 4b. 精確解：回溯（n 小） ----------
class BinPackExact {
    vector<int> items;
    int cap, best;
public:
    long long nodes = 0;
    int solve(vector<int> its, int cap_) {
        items = std::move(its);
        sort(items.begin(), items.end(), greater<int>());  // 大的先放，剪枝更兇
        cap = cap_;
        best = (int)items.size();
        nodes = 0;
        vector<int> space;
        dfs(0, space);
        return best;
    }
private:
    void dfs(int idx, vector<int>& space) {
        ++nodes;
        if ((int)space.size() >= best) return;             // 剪枝：不會更好
        if (idx == (int)items.size()) {
            best = (int)space.size();
            return;
        }
        int w = items[idx];
        for (int b = 0; b < (int)space.size(); ++b) {
            if (space[b] < w) continue;
            // 對稱剪枝：剩餘空間相同的箱子只試一個
            bool dup = false;
            for (int b2 = 0; b2 < b; ++b2)
                if (space[b2] == space[b]) { dup = true; break; }
            if (dup) continue;
            space[b] -= w;
            dfs(idx + 1, space);
            space[b] += w;
        }
        space.push_back(cap - w);                          // 開新箱
        dfs(idx + 1, space);
        space.pop_back();
    }
};

static void show(const string& tag, const Packing& p, int cap) {
    cout << tag << ": " << p.count() << " bins\n";
    for (int b = 0; b < p.count(); ++b) {
        int sum = accumulate(p.bins[b].begin(), p.bins[b].end(), 0);
        cout << "  bin" << b << " [";
        for (size_t i = 0; i < p.bins[b].size(); ++i)
            cout << p.bins[b][i] << (i + 1 < p.bins[b].size() ? "," : "");
        cout << "] used " << sum << "/" << cap << "\n";
    }
}

int main() {
    // ---- 範例 1：三種演算法一字排開 ----
    cout << "=== Example 1: NF vs FF vs FFD ===\n";
    vector<int> a = {4, 8, 1, 4, 2, 1};
    int cap = 10;
    cout << "items {4,8,1,4,2,1}, capacity 10, lower bound = "
         << lowerBound(a, cap) << "\n";
    show("NextFit ", nextFit(a, cap), cap);
    show("FirstFit", firstFit(a, cap), cap);
    show("FFD     ", firstFitDecreasing(a, cap), cap);
    cout << "\n";

    // ---- 範例 2：排序的威力——FFD 救回 FF 的失手 ----
    cout << "=== Example 2: why sorting helps ===\n";
    vector<int> b = {5, 5, 4, 4, 3, 3, 2, 2, 2};   // 總和 30，cap 10 -> 下界 3
    cout << "items {5,5,4,4,3,3,2,2,2}, capacity 10, lower bound = "
         << lowerBound(b, 10) << "\n";
    cout << "FF  bins = " << firstFit(b, 10).count() << "\n";
    cout << "FFD bins = " << firstFitDecreasing(b, 10).count() << "\n";
    show("FFD detail", firstFitDecreasing(b, 10), 10);
    cout << "\n";

    // ---- 範例 3：FFD 也非萬能——差 OPT 一箱的例子 ----
    cout << "=== Example 3: FFD is not optimal either ===\n";
    // 經典构造: cap=100, OPT=2 但 FFD=3 需要更大例；用精確解對照
    vector<int> c = {51, 27, 26, 23, 22, 21, 50, 50, 30};  // 總和 300
    BinPackExact ex;
    int opt = ex.solve(c, 100);
    cout << "items sum=300, capacity 100, lower bound = "
         << lowerBound(c, 100) << "\n";
    cout << "FFD   bins = " << firstFitDecreasing(c, 100).count() << "\n";
    cout << "exact bins = " << opt << " (nodes=" << ex.nodes << ")\n";
    show("FFD detail", firstFitDecreasing(c, 100), 100);
    cout << "\n";

    // ---- 範例 4：隨機實例統計——FFD 平常有多好 ----
    cout << "=== Example 4: FFD quality on random instances ===\n";
    unsigned seed = 20260724;
    auto nextRand = [&seed]() {
        seed = seed * 1103515245 + 12345;
        return (seed >> 16) & 0x7fff;
    };
    int trials = 100, ffdTotal = 0, optTotal = 0, ffdOptimal = 0;
    for (int t = 0; t < trials; ++t) {
        vector<int> items;
        for (int i = 0; i < 12; ++i) items.push_back(10 + nextRand() % 61);
        int f = firstFitDecreasing(items, 100).count();
        int o = ex.solve(items, 100);
        ffdTotal += f;
        optTotal += o;
        if (f == o) ++ffdOptimal;
    }
    cout << trials << " random instances (12 items, size 10-70, cap 100):\n";
    cout << "FFD optimal " << ffdOptimal << "/" << trials << " times, "
         << "avg FFD=" << (double)ffdTotal / trials
         << " vs avg OPT=" << (double)optTotal / trials << "\n";
    cout << "theory: FFD <= (11/9) OPT + 6/9, in practice usually spot-on\n";
    return 0;
}