審題：

本題需要我們找出將n個小貓放在有限重的纜車上運下山所需的最小纜車數

時間復雜度分析：本題的數據量小于等于18，所以我們在做好剪枝的前提下可以使用深度優先搜索解題

思路：

方法一：dfs

搜索策略：將小貓一個個的放入纜車中，有兩種放法：

第一種是放到當前已有纜車中，第二種是放到新的纜車中

剪枝策略：

剪枝1：可行性剪枝

我們需要在小貓重量+當前纜車中小貓總重小于等于限重時放入，若不滿足就剪枝

剪枝2：最優化剪枝

在我們已經搜索過的放法中，最小纜車數會被放到answer，若answer小于當前的纜車數c，那么說明該條路線已經不用搜索了，最優情況也就是等于answer。

剪枝3：優化搜索順序

優化1：先從體重較大的小貓開始放入，因為這樣可以更快搜索出較小的answer

優化2：先考慮已有的纜車放入，再考慮開新纜車，也是服務于剪枝2的

解題：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
int n, w;
int answer = N;
int c = 0;//當前車數
int cat[N], s[N];//cat負責記錄貓的體重，s記錄纜車當前負重

（1）main函數與compare函數

bool compare(int a,int b)//改變比較邏輯為降序
{return a > b;
}
int main()
{//錄入數據cin >> n >> w;for (int i = 1; i <= n; i++){cin >> cat[i];}//優化搜索順序sort(cat + 1, cat + n + 1, compare);dfs(1);//傳遞貓的索引cout << answer << endl;return 0;
}

這里我們進行剪枝3的優化1：先從較重的貓開始放入。

所以我們通過compare函數，自己實現大數據優先的降序sort

（2）dfs

void dfs(int pos)
{//剪枝：最優化搜索if (c >= answer){return;}//結束條件if (pos > n){answer = c;return;}//優先搜索不開新車情況for (int i = 1; i <= c; i++){//可行性剪枝if (cat[pos] + s[i] > w){continue;}s[i] += cat[pos];dfs(pos + 1);s[i] -= cat[pos];}//開新車情況c++;s[c] = cat[pos];dfs(pos + 1);s[c] = 0;c--;
}

結束條件：之所以可以直接讓c給到answer，是因為經過了剪枝最優化搜索的篩選，c一定是小于answer的，否則就被剪掉了

剪枝3：我們優先搜索不開新車的情況，所以把開新車情況放在for循環后，只有當所有舊的纜車都無法承載當前貓的體重時才會進入開新車的情況。

而所有的dfs搜索基本都涉及回退，有的是看情況回退，有的是一定回退，像這里這種搜索情況但是不記錄具體方法的就是一定回退，所以我們在dfs出來后要還原數據

P10483 小貓爬山 - 洛谷