DFS剪枝优化：小猫爬山

小猫爬山"/>

DFS剪枝优化：小猫爬山

问题描述

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

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

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

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

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

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

输入格式

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

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

数据范围：

1 ≤ N ≤ 18 1≤N≤18 1≤N≤18 , 1 ≤ C i ≤ W ≤ 1 0 8 1≤C_i≤W≤10^8 1≤Ci​≤W≤108

输出格式

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

输入样例

5 1996
1
2
1994
12
29

输出样例

2

算法思想（DFS + 剪枝）

对每只小猫来说要么安排在已有的缆车中，要么安排到新的缆车中。所以考虑如下搜索顺序：

1. 遍历已经安排的缆车，尝试将小猫放入
2. 将小猫放入新缆车

确定了搜索顺序，再考虑如何对搜索过程进行优化，这就是涉及到了DFS的剪枝技巧。

DFS常用剪枝技巧

1. 优化搜索顺序，大部分情况下，优先搜索分支较少的结点。配合最优性剪枝，可以大大提高搜索效率。对于本题来说，优先安排体重大的小猫，这样产生的分支结点少。
2. 排除等效冗余，例如搜索组合数，不考虑搜索顺序，排除重复搜索
3. 可行性剪枝，例如每辆缆车中的小猫重量不能超过其载重量
4. 最优性剪枝。在搜索过程中，如果发现该分支的结果不优于目前最优解，则可以结束对当前分支的搜索。
5. 记忆化搜索，在搜索过程中记录搜索结果，避免重复计算。

代码实现

#include <iostream>
#include <algorithm>using namespace std;const int N = 20;
int n, m, ans = N;
//w[i]表示第i只小猫的重量
//sum[i]表示第i个缆车的重量
int w[N], sum[N];//t表示当前搜索到的小猫
//k表示目前已经安排的缆车数量
void dfs(int t, int k)
{//最优性剪枝if(k >= ans) return;if(t == n){ans = k;return;}//将当前的小猫安排在已有缆车中for(int i = 0; i < k; i++){//如果当前小猫的重量 + 缆车i的重量 超过了 缆车的承重//可行性剪枝if(w[t] + sum[i] <= m){sum[i] += w[t];dfs(t + 1, k);sum[i] -= w[t];}}//将当前的小猫安排在新缆车中//注意：k的编号是从0开始的，所以这里将小猫安排在新缆车k中sum[k] = w[t];dfs(t + 1, k + 1);//恢复现场sum[k] = 0;
}int main()
{cin >> n >> m;for(int i = 0; i < n; i++) cin >> w[i];//按小猫体重从大到小排序//优化搜索顺序，优先搜索分支较少的结点sort(w, w + n);reverse(w, w + n);dfs(0, 0);cout << ans << endl;return 0;
}