小猫爬山

形式化题目

给定 $N$ 个重量 $C_1, C_2, \ldots, C_N$ 与容量 $W$ （保证每个 $C_i \leqslant W$ ），把它们划分成若干个互不相交的子集，使每个子集内的元素之和不超过 $W$ 。求所需子集个数的最小值。

以样例为例子集划分的一种最优方案：

车	装的小猫	总重量	是否超限
第 1 辆	$1994 + 2$	$1996$	恰好装满
第 2 辆	$29 + 12 + 1$	$42$	未超限

两只猫不能合用一车之外的其他可能都被排除后， $2$ 辆就是答案。要特别注意： $N \leqslant 18$ 很小，但 $W$ 可以到 $10^8$ ，所以不能对重量做任何与 $W$ 成正比的预处理。

正解

思路

这是经典的装箱问题（bin packing）：把 $N$ 件物品装进最少数量的容量 $W$ 的箱子。装箱问题是 NP 困难的，没有任何已知的多项式解法；但这里 $N \leqslant 18$ ，规模极小，所以正解是带剪枝的深度优先搜索。

第一步：把"装箱"翻译成"逐只做决定"。

不要去想"最后分成哪几堆"，而是一个一个地安排小猫：按某个顺序依次处理第 $i$ 只猫，这是搜索的阶段；对每只猫尝试两种动作——塞进某辆已经租好的车（前提是剩余空间装得下），或者新租一辆车。当第 $N$ 只猫也安置好，就得到一个可行方案，车数就是它的花费。

这样搜索的叶子节点集合与"所有合法划分"一一对应，只要枚举完，取最小的叶子深度就是答案。 $N=18$ 时最坏情况下每层分支数最多 $N$ ，节点数是 $O(N!)$ 级别，必须剪枝。

第二步：讨论顺序——从重到轻。

把猫按重量降序排序后再搜索。理由有两个：重的猫能落脚的候选车最少（剩余空间要 $\geqslant C_i$ ），分支最窄；而且重的猫排在前面，能更早把 best（当前搜到的最优车数）压小，后面的宽分支就都被剪掉。这一步不改变正确性，只是让同一棵搜索树变得更容易被剪。

第三步：能不能直接贪心？

很自然的想法是：按重量降序，每只猫塞进"还装得下它、且剩余空间最小"的那辆车（首次适应递减，FFD）。贪心很快，但它不保证最优。例如 $W = 19$ 、猫的重量是 $10, 7, 6, 5, 4, 3, 3$ ：

步骤	当前猫	已租车剩余空间	贪心的选择
1	$10$	空	新开车，剩 $9$
2	$7$	$9$	放进第 1 辆，剩 $2$
3	$6$	$2$	新开车，剩 $13$
4	$5$	$2, 13$	放进第 2 辆，剩 $8$
5	$4$	$2, 8$	放进第 2 辆，剩 $4$
6	$3$	$2, 4$	放进第 2 辆，剩 $1$
7	$3$	$2, 1$	两辆都装不下，新开车，共 $3$ 辆

贪心得到 $3$ 辆；但最优是 $10+6+3 = 19$ 与 $7+5+4+3 = 19$ 两辆。所以贪心只能当作剪枝用的可行上界，不能当答案。

第四步：三条剪枝。

记 best 为目前搜到的最小车数（初始值取贪心结果），space_left 为各已租车的剩余空间，free 为它们的总和。

车数剪枝：若已租车数 len(space_left) >= best，这个分支再往下走也不可能更优，立即返回。
剩余量下界剪枝：设 suffix[i] 为第 $i$ 只及以后（已按降序排好，也就是最重的那些）的重量和。现有空位一共只能再塞 free，剩下 suffix[i] - free 的重量必须靠新车，每辆车最多贡献 capacity，所以还要
$\left\lceil \frac{\texttt{suffix[i]} - \texttt{free}}{\texttt{capacity}} \right\rceil$
辆车。若 len(space_left) 加上它已经 $\geqslant$ best，同样剪掉。
"最重的几只"下界剪枝：这是最强的一条。固定起点 $i$ ，考虑第 $i$ 只及以后这 $n-i$ 只猫。对每个 $k$ ，取它们中最轻的 $k$ 只（即第 $i$ 到第 $i+k-1$ 只里第 $i+k-1$ 只最轻，重量为 $c = C_{i+k-1}$ ）。任何一辆车装的猫都 $\geqslant c$ ，所以一辆车最多装 $\lfloor W / c \rfloor$ 只，装完这 $k$ 只至少要
$\left\lceil \frac{k}{\lfloor W / c \rfloor} \right\rceil$
辆车。对所有 $k$ 取最大值，就得到"第 $i$ 只及以后至少要几辆车"的下界 least[i]，与当前怎么装无关。若 least[i] >= best，这个子树不可能更优。

第五步：对称性去重。

不同的车如果剩余空间相同，它们在结构上完全等价：把猫放进其中任何一辆，得到的后续状态（剩余空间的多重集）一模一样。用一个 tried 集合记住本次已经试过哪些剩余空间，同一个值只试一辆，直接砍掉大部分重复分支。这一步也用到了 cats 已降序：同一只猫放进剩余空间大的车，剩下的小车就更装不下后面较小的猫，剪枝效果更好。

把这几步合起来，就能在 $N=18$ 时快速搜完。下图的搜索树片段取自第二步里的贪心反例（ $W=19$ ，猫为 $10, 7, 6, 5, 4, 3, 3$ ），可以看清剪枝发生在哪里。

flowchart TD
  A["放 10：新开一辆，剩 9"] --> B["放 7：放进车1，剩 2"]
  B --> C["放 6：新开车2，剩 13"]
  C --> D["放 5：放进车2，剩 8"]
  D --> E["放 4：放进车2，剩 4"]
  E --> F["放 3：放进车2，剩 1"]
  F --> G["放 3：新开车3 → best=3"]
  G --> H["回溯：同一层 len>=best 剪枝"]
  F --> I["放 3：新开车，3>=3 剪枝"]
  D --> J["放 5：新开车，3>=best 剪枝"]

图中第一段路径找到的是 $3$ 辆的可行方案（对应贪心结果），随后回溯发现第二辆车还剩 $9$ 时先放 $6$ 而不是 $5$ ，能让第 6、7 只 $3$ 也塞进同一辆车，于是 $best$ 降到 $2$ ；此后所有已用 $3$ 辆车的分支都在进门那一行被 len(space_left) >= best 挡掉。

对应的代码如下。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 12:54
# update_at: 2026-10-01 12:54

import sys


def fit_first(cats: list[int], capacity: int) -> int:
    """贪心：重的猫先来，塞进剩余空间最小、又还装得下的那辆车，返回车数。"""
    space_left: list[int] = []
    for weight in cats:
        pick, gap = -1, None  # gap 记录候选车里最小的剩余空间
        for j, space in enumerate(space_left):
            if space >= weight and (gap is None or space < gap):
                gap, pick = space, j
        if pick < 0:
            space_left.append(capacity - weight)
        else:
            space_left[pick] -= weight
    return len(space_left)


def fewest_cars(cats: list[int], capacity: int) -> int:
    """把已按重量降序排好的猫装进容量为 capacity 的车，返回最少车数。"""
    n = len(cats)
    # 贪心不保证最优，但它给出的车数一定可行，可以直接当搜索的上界
    best = fit_first(cats, capacity)
    space_left: list[int] = []  # 每辆已租车的剩余空间，车的数量就是 len(space_left)
    free = 0  # space_left 里所有空位之和

    # 下界一：第 i 只及以后是最重的几只，把它们按「每辆车都恰好装满」的最优情况
    # 摊开，车数只可能更少，所以这个值是剩余部分的车数下界。
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + cats[i]
    least = [1] * (n + 1)  # least[i] = 第 i 只及以后至少还要几辆车
    for i in range(n):
        for k in range(1, n - i + 1):
            # 这一组最轻的是 cats[i+k-1]，每辆车最多装 W // cats[i+k-1] 只
            group = -(-k // max(1, capacity // cats[i + k - 1]))
            if group > least[i]:
                least[i] = group

    def dfs(i: int) -> None:
        """决定第 i 只猫坐哪辆车：要么塞进某辆已租车，要么新租一辆。"""
        nonlocal best, free
        if len(space_left) >= best:  # 已租车数不优于当前最优解
            return
        if i == n:
            best = len(space_left)  # 所有猫都上车，得到一个更优解
            return
        if least[i] >= best:  # 剩下最重的这几只至少还要这么多车
            return
        # 下界二：现有空位塞不下的重量，每 capacity 必须再开一辆新车
        if len(space_left) + -(-(suffix[i] - free) // capacity) >= best:
            return
        weight = cats[i]
        tried = set()  # 剩余空间相同的车完全对称，只需要试其中一辆
        for j, space in enumerate(space_left):
            if space >= weight and space not in tried:
                tried.add(space)
                space_left[j] = space - weight
                dfs(i + 1)
                space_left[j] = space
        space_left.append(capacity - weight)  # 新租一辆车，这辆只装它一只
        free += capacity - weight
        dfs(i + 1)
        free -= space_left.pop()  # 回溯：撤掉这辆新车

    dfs(0)
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, capacity = next(data), next(data)
    # 先安排重的猫：重猫可选的落点少，尽早定下来能更快收紧 best，剪掉更多分支
    cats = sorted((next(data) for _ in range(n)), reverse=True)

    print(fewest_cars(cats, capacity))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 17:02
 * update_at: 2026-10-06 17:02
 */

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 20; // N <= 18

ll n, capacity;
ll cat[MAXN];        // 按重量降序排列的猫
ll space_left[MAXN]; // 每辆已租车的剩余空间
ll suffix[MAXN];     // suffix[i] = 第 i 只及以后猫的重量和
ll least[MAXN];      // least[i] = 第 i 只及以后至少还要几辆车
ll best;             // 当前搜到的最小车数
ll free_sum;         // 所有已租车剩余空间之和
int car_cnt;         // 当前已租车数

// 贪心：按重量降序，每只猫塞进剩余空间最小且能装下的车，返回车数上界
ll fit_first() {
    vector<ll> spaces;
    for (int i = 0; i < n; i++) {
        ll weight = cat[i];
        int pick = -1;
        ll min_space = capacity + 1;
        for (int j = 0; j < (int)spaces.size(); j++) {
            if (spaces[j] >= weight && spaces[j] < min_space) {
                min_space = spaces[j];
                pick = j;
            }
        }
        if (pick < 0) {
            spaces.push_back(capacity - weight);
        } else {
            spaces[pick] -= weight;
        }
    }
    return (ll)spaces.size();
}

// 预处理 suffix 与 least 下界数组
void preprocess() {
    suffix[n] = 0;
    for (int i = n - 1; i >= 0; i--) {
        suffix[i] = suffix[i + 1] + cat[i];
    }
    for (int i = 0; i < n; i++) {
        least[i] = 1;
        for (int k = 1; k <= n - i; k++) {
            // 第 i 只及以后最轻的 k 只中，最重的是 cat[i+k-1]
            ll per_car = capacity / cat[i + k - 1];
            if (per_car == 0) per_car = 1;
            ll need = (k + per_car - 1) / per_car;
            if (need > least[i]) least[i] = need;
        }
    }
}

// 第 dep 只猫选择落点：放进某辆已租车，或新租一辆
void dfs_choose(int dep) {
    if (car_cnt >= best) return; // 已用车数不优于当前最优解
    if (dep == n) {
        best = car_cnt; // 所有猫都安置完毕
        return;
    }
    if (least[dep] >= best) return; // 剩余最重几只的车数下界
    // 现有空位塞不下的重量还需 ceil((suffix[dep] - free_sum) / capacity) 辆车
    ll need = (suffix[dep] - free_sum + capacity - 1) / capacity;
    if (car_cnt + need >= best) return;

    ll weight = cat[dep];
    ll tried[MAXN]; // 本层已经试过的剩余空间值
    int tried_cnt = 0;

    // 尝试放进已有的车，剩余空间相同的车只试一辆
    for (int i = 0; i < car_cnt; i++) {
        if (space_left[i] < weight) continue;
        bool same = false;
        for (int j = 0; j < tried_cnt; j++) {
            if (tried[j] == space_left[i]) {
                same = true;
                break;
            }
        }
        if (same) continue;
        tried[tried_cnt++] = space_left[i];

        space_left[i] -= weight;
        free_sum -= weight;
        dfs_choose(dep + 1);
        space_left[i] += weight;
        free_sum += weight;
    }

    // 新租一辆车
    space_left[car_cnt] = capacity - weight;
    free_sum += capacity - weight;
    car_cnt++;
    dfs_choose(dep + 1);
    car_cnt--;
    free_sum -= capacity - weight;
}

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

    cin >> n >> capacity;
    for (int i = 0; i < n; i++) {
        cin >> cat[i];
    }
    // 按重量降序：重猫分支窄，能更快收紧 best
    sort(cat, cat + n, greater<ll>());

    preprocess();
    best = fit_first();
    car_cnt = 0;
    free_sum = 0;
    dfs_choose(0);

    cout << best << "\n";
    return 0;
}

复杂度

时间复杂度：最坏 $O(N!)$ （每层最多 $N$ 种落点），也就是枚举全部划分的规模；降序 + 三条下界剪枝 + 对称去重后， $N \leqslant 18$ 的实际搜索量远小于上界，真实数据均在毫秒级。
空间复杂度： $O(N)$ ，递归深度与 space_left、suffix、least 都只有 $N$ 项。

正确性要点

不漏解：每一只猫只有"进已有车"和"开新车"两类落点，任何合法划分（把每辆车按其中第一只猫被处理的时刻视为"开新车"）都能在搜索树上找到唯一路径，因此最优解一定被枚举到。
剪枝不误杀：三条下界（已用车数、剩余重量、最重几只的每车件数）都只用于"这个子树不可能比 best 更好"的判定，只会跳过不优的分支；best 初值来自一个可行方案，故答案始终可行。
边界： $N = 1$ 时贪心直接返回 $1$ ；所有 $C_i = W$ 时每只猫各占一车，贪心给出 $N$ ，剪枝立刻终止；题面保证 $C_i \leqslant W$ ，代码不必处理装不下的猫。

总结

装箱问题是 NP 困难的，但 $N \leqslant 18$ 允许搜索 + 剪枝：把"划分"改写成一维的"逐只猫做决定"。
降序排序是这类搜索的固定套路：重物分支窄、能更早压紧上界。
贪心（首次适应递减）拿不到最优解，但可以提供一个便宜又紧的上界，让剪枝从第一步就生效。
三条剪枝互补：车数下界管"已经开太多车"，剩余重量下界管"后面还得再开几辆"，每车件数下界管"最重的这几只无论如何都装不完"。
剩余空间相同的车互为对称，同一层只试一次即可，这是本题最简单也最有效的一刀。

目录

形式化题目

正解

思路

代码

复杂度

正确性要点

总结