题目描述

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

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

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

索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN。

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

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

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

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

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

数据范围
1≤N≤18,
1≤Ci≤W≤108
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2

算法1

常规DFS解决， 有序的遍历将猫放进现有车辆以及新开车辆的各种组合
不过要加上剪枝 避免不必要的运算。
比如每个猫都开一辆新车，当新车的数量比已知的答案还要多的时候，就不必继续运算了

C++ 代码

// 1111111111111111111.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


/*
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2
*/

/*
4 10
5
6
3
7
===========
3
*/

const int N = 30;

int arr[N];
int car[N];
int ans = 99999999;
int n, limit;

void dfs(int catC,int carC) {
    if (catC == n) {
        ans = min(carC, ans);
        return;
    }

    if (carC >= ans) return;

    for (int i = 1; i <= carC; i++) {
        //如果当前的车 可以放入猫 则尝试放入猫
        if ((car[i] + arr[catC]) <= limit) {
            car[i] += arr[catC];
            dfs(catC + 1, carC);
            //还原场景
            car[i] -= arr[catC];
        }
    }

    //尝试新开一个车厢 放入猫
    carC++;
    car[carC] += arr[catC];
    dfs(catC + 1, carC);
    car[carC] -= arr[catC];
    carC--;
}


int main()
{
    cin >> n >> limit;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }


    dfs(0,1);

    cout << ans << endl;




    return 0;
}

我的视频题解空间