《算法竞赛进阶指南》 小猫爬山--题解

题目描述
Freda和rainbow饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

输入描述:
Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是 。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？

输出描述:
第一行包含两个用空格隔开的整数，N和W。
接下来N行每行一个整数，其中第i+1行的整数表示第i只小猫的重量 。

思路：
狗粮题（划掉）。看题目发现n特别小，重量特别大，所以不能背包，只能搜索。如果直接爆搜的话，迟早会TLE（我太难了.jpg）。所以可以发现有两个可以剪枝的部分：

1. 若 k >= ans 直接return。
2. 我们可以将小猫的体重从大到小排序,这样我们的搜索树就会缩短许多,因为我们的剩余空间就变小了,然后可选择的猫也就少了.

完整C++版AC代码：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 20;

int cat[N];//存每只猫的重量
int p[N];//存当前车上所有的重量

int n, w;
int ans = N;

void dfs(int u, int k) {//u代表当前是哪一只猫，k代表当前是第几辆缆车

    if (k > ans) return;//剪枝
    if (u == n)
    {
        ans = k;//也可以写成 ans = min (ans, k);
        return;

    }

    for (int i = 0; i < k; i++) {
        if (p[i] + cat[u] <= w) {//将当前这只cat放到前k个缆车上（枚举前k个缆车，判断是否能放入）
            p[i] += cat[u];
            dfs(u + 1, k);
            p[i] -= cat[u];
        }
    }
    p[k] = cat[u];//开新车
    dfs(u + 1, k + 1);
    p[k] = 0;
}

int main() {

    cin >> n >> w;
    for (int i = 0; i < n; i++)
        cin >> cat[i];

    sort(cat, cat + n);
    reverse(cat, cat + n);//从大到小排序，这里也可以手动写个cmp。

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}