题目描述

链接：https://ac.nowcoder.com/acm/contest/1014/A
来源：牛客网
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

思路

首先将小猫的重量从大到小排序，然后使用深度优先搜索按顺序将每只小猫尽可能安排在数量少的缆车上。当每只猫都被安排好后判断所用缆车数量，得到最小值。

代码

#include<iostream>
using namespace std;
int n,w,ans;
int Cable_Car[19],cat[19];
void sort(int* cat)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (cat[j] > cat[i])
            {
                int t = cat[j];
                cat[j] = cat[i];
                cat[i] = t;
            }
        }
    }
}
void dfs(int c,int p)//c代表当前是哪只猫，p是缆车，从0开始数。
{
    if (p > ans)return;
    if (c == n)
    {
        ans = p;
        return;
    }
    for (int i = 0; i < p; i++)
    {
        if ((Cable_Car[i] + cat[c]) <= w)
        {
            Cable_Car[i] += cat[c];
            dfs(c + 1, p);
            Cable_Car[i] -= cat[c];
        }
    }
    Cable_Car[p] = cat[c];
    dfs(c + 1, p + 1);
    Cable_Car[p] = 0;
}
int main()
{
    cin >> n >> w;
    ans = n;
    for (int i = 0; i < n; i++)
    {
        cin >> cat[i];
        Cable_Car[i] = 0;
    }
    sort(cat);
    dfs(0, 0);
    cout << ans;
    return 0;
}