题目链接

算法竞赛进阶指南-79.小猫爬山

翰翰和达达饲养了 $N$ 只小猫，这天，小猫们要去爬山。

经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 $W$，而 $N$ 只小猫的重量分别是 $C_1、C_2……C_N$。

当然，每辆缆车上的小猫的重量之和不能超过 $W$。

每租用一辆缆车，翰翰和达达就要付 $1$ 美元，所以他们想知道，最少需要付多少美元才能把这 $N$ 只小猫都运送下山？

输入格式

第 $1$ 行：包含两个用空格隔开的整数，$N$ 和 $W$。

第 $2..N+1$ 行：每行一个整数，其中第 $i+1$ 行的整数表示第 $i$ 只小猫的重量 $C_i$。

输出格式

输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

数据范围

$1 \le N \le 18$,
$1 \le C_i \le W \le 10^8$

输入样例：

5 1996
1
2
1994
12
29

输出样例：

2

Method : DFS

非常典型的一道dfs题目，直接dfs会超时，需要剪枝优化：

dfs(int u, int k)

• 优化搜索顺序：将小猫重量从小到大逆序排序，先搜索重量较大的小猫，这样上层搜索分支就会减少，有利于减少整体分支数量
• 最优性剪枝：设定全局最小值，当搜索的任何时刻发现 k 已经>=当前res，则当前分支直接回溯

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 18 + 7;

int n, w;
int cat[N], sum[N];
int res = N;

void dfs(int u, int k) {
    // boundary
    if (u == n) {
        res = min(res, k);
        return;
    }
    // prune
    if (k >= res) return;
    
    for (int i = 0; i < k; i ++) {
        if (sum[i] + cat[u] <= w) {
            sum[i] += cat[u];
            dfs(u + 1, k);
            // recover
            sum[i] -= cat[u];
        } 
    }
    sum[k] += cat[u];
    dfs(u + 1, k + 1);
    // recover
    sum[k] = 0;
}

int main() {
    memset(sum, 0 ,sizeof sum);
    
    cin >> n >> w;
    for (int i = 0; i < n; i ++) {
        scanf("%d", &cat[i]);
    }
    
    // 优先考虑决策少的元素
    sort(cat, cat + n, [](const int a, const int b) {
        return a > b;
    });
    
    dfs(0, 1);
    
    cout << res << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：最坏情况下${O(n^2)}$， 每次最多多出k条路径，k最大为n，但由于剪枝，实际会远小于该复杂度。

• 空间复杂度：${O(N)}$。

Other

一开始写了一个基于set的贪心方法，每次找当前尽可能能满足的最大重量的🐱，但是这并不是最优解。

#include <set>
#include <iostream>

using namespace std;
const int N = 18 + 7;

set<int> c;
int n, w;

int main() {
    cin >> n >> w;
    for (int i = 0; i < n; i ++) {
        int x;
        scanf("%d", &x);
        c.insert(x);
    }
    
    int res = 0;
    while (!c.empty()) {
        int remain = w;
        while (remain) {
            auto it_upper = c.upper_bound(remain);
            if (it_upper != c.begin()){
                auto upper = prev(it_upper);
                remain -= *upper;
                c.erase(upper);
            }
            else {
                break;
            }
        }
        res ++;
    }
    
    cout << res << endl;
    
    return 0;
}