算法题：小猫爬山

问题描述

Freda和rainbow饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。 Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是C1,C2,…,CN。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？

输入格式

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

输出格式

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

样例

输入

5 1996
1
2
1994
12
29

输出

2

数据范围

对于100%的数据，1≤N≤18，1≤Ci≤W≤108。

解决方案

思路

深度优先搜索

代码

#include <iostream>
#include <algorithm>

using namespace std;

int n, w;
int arr[100];

int pos[100];
int ans = 0x3c3c3c3c;

bool cmp(int a, int b) {
    return a > b;
}

// 深度搜索每个小猫
void dfs(int x, int h = 1) {
    if (h >= ans) return;
    if (x == n) {
        ans = min(ans, h);
        return;
    }

    // 遍历每个缆车
    for (int i = 1; i <= h; ++i) {

        if (arr[x] + pos[i] <= w) {
            pos[i] += arr[x];
            dfs(x + 1, h);
            pos[i] -= arr[x];
        }
    }
    
    //缆车不够，加一个缆车
    pos[h + 1] = arr[x];
    dfs(x + 1, h + 1);
    pos[h + 1] = 0;
}

int main() {

    scanf("%d%d", &n, &w);
    ans = n;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }
    // 排序让大的放到前面，这样可以加快速度
    sort(arr, arr + n, cmp);
    dfs(0);
    cout << ans;

    return 0;
}