题目描述

N<20,数据范围小，典型用dfs
N 只小猫的重量分别是 C1、C2……CN。
索道上的缆车最大承重量为 W
当然，每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？
输入格式
第 1 行：包含两个用空格隔开的整数，N 和 W。
第 2..N+1 行：每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。

算法1

(dfs)

dfs(int u, int k) //u表示遍历到第u个猫，k表示遍历到前k个车装了猫

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n, m;
int cat[N]; //猫的重量
int sum[N]; //车的承重
int ans = N; //最优结果
void dfs(int u, int k)  //u表示遍历到第u个猫，k表示遍历到前k个车装了猫
{
//判断超过ans，或者遍历到n个猫（更新答案）
    if (k >= ans) return;   //前k（>ans）个车装了猫，不是最优结果，直接返回
    if (u == n) {   //遍历到最后一个猫，得到一个较优结果
        ans = k;   //更新最优结果
        return;     
    }
    //第一个方案：加入已有猫的车
    for (int i = 0; i < k; i++)  //遍历前k个车
        if (cat[u] + sum[i] <= m) {  //第u个猫加上，车原来装的重量，<=上限
            sum[i] += cat[u]; 
            dfs(u + 1, k); //遍历下一个猫
            sum[i] -= cat[u];  //回溯
        }
    //第二个方案：加入新车
    sum[k] = cat[u];  //放到一个新车
    dfs(u + 1,k + 1);  //递归
    sum[k] = 0;    //回溯
}
int main() 
{
    cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> cat[i];
    sort(cat,cat + n);
    reverse(cat, cat + n);  //逆序
    /*遮去上面两句，程序依旧可以运行，只是时间消耗会更多*/
    /*加上这两句，只要20ms，删去，要90s*/
    dfs(0,0);
    cout << ans << endl; 
    return 0;
}