DFS 剪枝：可行性、最优性、搜索顺序

// 小猫爬山 —— 朴素 DFS，一个剪枝都不加
//
// 输入：第一行 n W（n 只猫，每辆缆车最大载重 W）
//       第二行 n 个整数，第 i 只猫的重量 w[i]（保证 w[i] <= W）
// 输出：最少需要几辆缆车
//
// 每辆车可以载任意多只猫，只要总重不超过 W。
//
// 搜索的形状（第 4 章那个框架）：
//     一只一只地安排猫。第 i 只猫有两类选择：
//         1. 塞进某一辆**已经开出去的**车（如果装得下）
//         2. 新开一辆车
//     全部安排完之后，用了几辆车就是一个候选答案。
//
// 这份代码**除了「装不下就不能塞」之外没有任何剪枝**，
// 所以它会把整棵搜索树走完。n 一大就彻底跑不动。
//
// 它是正确的，所以可以当对拍的标准答案 —— 但只能喂小数据。

#include <bits/stdc++.h>
using namespace std;

int n;
long long W;
vector<long long> w;
vector<long long> load;      // load[j] = 第 j 辆车已经装了多重
int carCount = 0;            // 已经开出去几辆车
int best;
long long nodes = 0;         // 统计一下总共进了多少次 dfs

void dfs(int i) {
    nodes++;

    if (i == n) {                       // 所有猫都安排完了
        best = min(best, carCount);
        return;
    }

    // 选择一：塞进已经开出去的某一辆车
    for (int j = 0; j < carCount; j++) {
        if (load[j] + w[i] <= W) {      // 唯一的「可行性」判断
            load[j] += w[i];
            dfs(i + 1);
            load[j] -= w[i];            // 撤销（第 4 章的三段式）
        }
    }

    // 选择二：新开一辆车
    load[carCount] = w[i];
    carCount++;
    dfs(i + 1);
    carCount--;
    load[carCount] = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> W)) return 0;
    w.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> w[i];

    load.assign(n + 1, 0);
    best = n;                            // 最坏情况：一只猫一辆车

    if (n > 0) dfs(0);
    cout << best << "\n";
    return 0;
}

// 小猫爬山 —— 同样的搜索，加满剪枝
//
// 输入输出和 brute.cpp 完全一样。**搜索的形状一点没变**，
// 变的只是「哪些分支根本不用走」。
//
// ============ 剪枝三板斧 ============
//
// 【1】搜索顺序：**先安排重的猫**（把 w 从大到小排序）
//     重的猫选择少、最容易失败。把它们放在前面，错误的分支会**很早**就撞墙，
//     而不是等到搜到底才发现不行。
//     ⚠ 注意：排序本身**不剪掉任何分支**，单独用几乎没有效果（跑 count.cpp 看③）。
//     它的作用是「放大器」：让搜索很早就摸到一个不错的解，best 迅速变小，
//     于是下面那条最优性剪枝变得凶狠得多。**两者要配合用。**
//
// 【2】最优性剪枝：**当前车数已经 >= 已知最优解，立刻返回**
//     再往下搜，最好的结果也只是追平，不可能更好，那就没必要搜。
//     注意它依赖「已经找到过一个解」—— 所以要先让搜索尽快摸到一个可行解
//     （靠【1】的排序，第一条路径通常就相当不错）。
//
// 【3】可行性剪枝：**装不下就不进这个分支**
//     这个 brute.cpp 里就有（`load[j] + w[i] <= W`），
//     它是最基本的一类：这条路走下去必然违反规则，不用走。
//
// 三板斧的通用说法：
//     可行性剪枝 = 「这条路走下去一定违规」
//     最优性剪枝 = 「这条路走下去一定不如已有答案」
//     搜索顺序   = 「先走最容易失败 / 最容易出好结果的分支」
//
// 到底能省多少？跑一下 count.cpp，它把四种组合的搜索节点数并排数给你看。

#include <bits/stdc++.h>
using namespace std;

int n;
long long W;
vector<long long> w, load;
int carCount = 0, best;

void dfs(int i) {
    if (carCount >= best) return;       // 【2】最优性剪枝

    if (i == n) { best = carCount; return; }

    for (int j = 0; j < carCount; j++) {
        if (load[j] + w[i] <= W) {      // 【3】可行性剪枝
            load[j] += w[i];
            dfs(i + 1);
            load[j] -= w[i];
        }
    }

    load[carCount] = w[i];
    carCount++;
    dfs(i + 1);
    carCount--;
    load[carCount] = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> W)) return 0;
    w.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> w[i];

    sort(w.begin(), w.end(), greater<long long>());   // 【1】搜索顺序：从重到轻

    load.assign(n + 1, 0);
    best = n;

    if (n > 0) dfs(0);
    cout << best << "\n";
    return 0;
}

// 小猫爬山 —— 把搜索过程和每一次剪枝打印出来
//
// 输入：n W / n 个重量（用小数据，n <= 8）
// 输出：每一步「把第 i 只猫放进第几辆车」，以及每一次剪枝的原因
//
// 盯住两种行：
//   ✂ 最优性剪枝 —— 车数已经追平当前最优，再往下搜没有意义，整片子树砍掉
//   ✗ 装不下     —— 可行性剪枝，这一辆车塞不下这只猫
//
// 把输入的猫按不同顺序给（比如手动改成从轻到重），
// 再对比一下「进入 dfs 的次数」—— 顺序真的会差很多。

#include <bits/stdc++.h>
using namespace std;

int n;
long long W;
vector<long long> w, load;
int carCount = 0, best;
long long nodes = 0, cuts = 0;

void indent(int d) { for (int i = 0; i < d; i++) cout << "|   "; }

void dfs(int i) {
    nodes++;

    if (carCount >= best) {
        cuts++;
        indent(i);
        cout << "✂ 已经用了 " << carCount << " 辆车，不比当前最优（" << best
             << " 辆）更好 —— 这一整片分支不用看了\n";
        return;
    }

    if (i == n) {
        indent(i);
        cout << "★ 全部安排完，用了 " << carCount << " 辆车";
        if (carCount < best) { cout << " —— 刷新最优！"; best = carCount; }
        cout << "\n";
        return;
    }

    for (int j = 0; j < carCount; j++) {
        indent(i);
        cout << "猫 " << i << "（重 " << w[i] << "）试第 " << j << " 号车（已装 " << load[j] << "）：";
        if (load[j] + w[i] <= W) {
            cout << "装得下 ✓\n";
            load[j] += w[i];
            dfs(i + 1);
            load[j] -= w[i];
        } else {
            cuts++;
            cout << "✗ 装不下（" << load[j] << " + " << w[i] << " > " << W << "）\n";
        }
    }

    indent(i);
    cout << "猫 " << i << " 新开一辆车（第 " << carCount << " 号）\n";
    load[carCount] = w[i];
    carCount++;
    dfs(i + 1);
    carCount--;
    load[carCount] = 0;
}

int main() {
    if (!(cin >> n >> W)) return 0;
    if (n <= 0 || n > 8) { cout << "这份是用来看过程的，请用 1 <= n <= 8\n"; return 0; }

    w.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> w[i];
    sort(w.begin(), w.end(), greater<long long>());

    cout << "从重到轻排序后：";
    for (int i = 0; i < n; i++) cout << w[i] << " ";
    cout << "　载重上限 " << W << "\n\n";

    load.assign(n + 1, 0);
    best = n;
    dfs(0);

    cout << "\n答案：" << best << " 辆车\n";
    cout << "进入 dfs 的次数：" << nodes << "　被剪掉的分支：" << cuts << "\n";
    return 0;
}

// 剪枝到底省了多少 —— 四种组合并排数给你看
//
// 输入：n W / n 个重量（用中等规模，n = 14 ~ 17 最有观感）
// 输出：一张表，四种剪枝组合各自访问了多少个搜索节点、用了多久
//
//     ① 什么都不加
//     ② 只加最优性剪枝
//     ③ 只加搜索顺序（从重到轻）
//     ④ 两个都加
//
// 这份代码不解新题，它只是把「剪枝值多少钱」变成具体数字。
//
// ★ 请特别对比 ③ 和 ④ 这两行，它们说的是一件很反直觉的事：
//
//   ③ 只排序、不加最优性剪枝 —— 几乎没用（整棵树照样走完）。
//      因为排序本身**不剪掉任何分支**，它只是换了个走的顺序。
//   ④ 排序 + 最优性剪枝 —— 比只加最优性剪枝（②）又快了十倍以上。
//
// 结论：**搜索顺序不是剪枝，它是剪枝的放大器。**
//   先安排重的猫，能让搜索很早就摸到一个不错的解，
//   于是 best 很快变小，最优性剪枝随之变得凶狠。
//   两者单独都不够，配合起来才厉害。

#include <bits/stdc++.h>
using namespace std;

int n;
long long W;
vector<long long> w0, w, load;
int carCount, best;
long long nodes;
bool useBestCut;

void dfs(int i) {
    nodes++;
    if (useBestCut && carCount >= best) return;

    if (i == n) { best = min(best, carCount); return; }

    for (int j = 0; j < carCount; j++) {
        if (load[j] + w[i] <= W) {
            load[j] += w[i];
            dfs(i + 1);
            load[j] -= w[i];
        }
    }

    load[carCount] = w[i];
    carCount++;
    dfs(i + 1);
    carCount--;
    load[carCount] = 0;
}

/** 跑一遍，返回 {答案, 节点数, 毫秒} */
void runOnce(bool sortDesc, bool bestCut, int& ansOut, long long& nodesOut, double& msOut) {
    w = w0;
    if (sortDesc) sort(w.begin(), w.end(), greater<long long>());
    load.assign(n + 1, 0);
    carCount = 0;
    best = n;
    nodes = 0;
    useBestCut = bestCut;

    auto t0 = chrono::steady_clock::now();
    if (n > 0) dfs(0);
    auto t1 = chrono::steady_clock::now();

    ansOut = best;
    nodesOut = nodes;
    msOut = chrono::duration<double, milli>(t1 - t0).count();
}

int main() {
    if (!(cin >> n >> W)) return 0;
    if (n <= 0 || n > 20) { cout << "请用 1 <= n <= 20（不加剪枝那一栏会跑不完）\n"; return 0; }

    w0.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> w0[i];

    struct Row { const char* name; bool sortDesc, bestCut; };
    Row rows[4] = {
        {"① 什么都不加        ", false, false},
        {"② 只加最优性剪枝    ", false, true},
        {"③ 只把猫从重到轻排序", true,  false},
        {"④ 两个都加          ", true,  true},
    };

    cout << "n = " << n << "，载重上限 W = " << W << "\n\n";
    cout << "组合                      答案      搜索节点数        耗时(ms)\n";
    cout << "----------------------  ------  --------------  --------------\n";

    long long baseNodes = -1;
    for (auto& r : rows) {
        int ans; long long nd; double ms;
        runOnce(r.sortDesc, r.bestCut, ans, nd, ms);
        if (baseNodes < 0) baseNodes = nd;
        cout << r.name << setw(8) << ans << setw(16) << nd
             << setw(16) << fixed << setprecision(2) << ms << "\n";
    }

    int ans; long long nd; double ms;
    runOnce(true, true, ans, nd, ms);
    cout << "\n全开之后，搜索节点数是原来的 1/" << (nd > 0 ? baseNodes / nd : 0) << " 左右。\n";
    cout << "注意：四种组合的**答案完全一样** —— 剪枝只砍掉了不可能更优的分支，\n";
    cout << "      它不会改变答案，只会让你更快地拿到它。\n";
    return 0;
}

// 小猫爬山 —— 同样的搜索，加满剪枝
//
// 输入输出和 brute.cpp 完全一样。**搜索的形状一点没变**，
// 变的只是「哪些分支根本不用走」。
//
// ============ 剪枝三板斧 ============
//
// 【1】搜索顺序：**先安排重的猫**（把 w 从大到小排序）
//     重的猫选择少、最容易失败。把它们放在前面，错误的分支会**很早**就撞墙，
//     而不是等到搜到底才发现不行。
//     ⚠ 注意：排序本身**不剪掉任何分支**，单独用几乎没有效果（跑 count.cpp 看③）。
//     它的作用是「放大器」：让搜索很早就摸到一个不错的解，best 迅速变小，
//     于是下面那条最优性剪枝变得凶狠得多。**两者要配合用。**
//
// 【2】最优性剪枝：**当前车数已经 >= 已知最优解，立刻返回**
//     再往下搜，最好的结果也只是追平，不可能更好，那就没必要搜。
//     注意它依赖「已经找到过一个解」—— 所以要先让搜索尽快摸到一个可行解
//     （靠【1】的排序，第一条路径通常就相当不错）。
//
// 【3】可行性剪枝：**装不下就不进这个分支**
//     这个 brute.cpp 里就有（`load[j] + w[i] <= W`），
//     它是最基本的一类：这条路走下去必然违反规则，不用走。
//
// 三板斧的通用说法：
//     可行性剪枝 = 「这条路走下去一定违规」
//     最优性剪枝 = 「这条路走下去一定不如已有答案」
//     搜索顺序   = 「先走最容易失败 / 最容易出好结果的分支」
//
// 到底能省多少？跑一下 count.cpp，它把四种组合的搜索节点数并排数给你看。

#include <bits/stdc++.h>
using namespace std;

int n;
long long W;
vector<long long> w, load;
int carCount = 0, best;

void dfs(int i) {
    if (carCount >= best) return;       // 【2】最优性剪枝

    if (i == n) { best = carCount; return; }

    for (int j = 0; j < carCount; j++) {
        if (load[j] + w[i] <= W) {      // 【3】可行性剪枝
            load[j] += w[i];
            dfs(i + 1);
            load[j] -= w[i];
        }
    }

    load[carCount] = w[i];
    carCount++;
    dfs(i + 1);
    carCount--;
    load[carCount] = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> W)) return 0;
    w.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> w[i];

    sort(w.begin(), w.end(), greater<long long>());   // 【1】搜索顺序：从重到轻

    load.assign(n + 1, 0);
    best = n;

    if (n > 0) dfs(0);
    cout << best << "\n";
    return 0;
}