代码
/*
* Project: 0x22_深度优先搜索
* File Created:Sunday, January 24th 2021, 11:31:12 am
* Author: Bug-Free
* Problem:AcWing 165. 小猫爬山
*/
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 2e1;
int cat[N], cab[N];
int n, w;
int ans;
bool cmp(int a, int b) {
return a > b;
}
void dfs(int now, int cnt) {
if (cnt >= ans) {
return;
}
if (now == n + 1) {
ans = min(ans, cnt);
return;
}
//尝试分配到已经租用的缆车上
for (int i = 1; i <= cnt; i++) { //分配到已租用缆车
if (cab[i] + cat[now] <= w) {
cab[i] += cat[now];
dfs(now + 1, cnt);
cab[i] -= cat[now]; //还原
}
}
// 新开一辆缆车
cab[cnt + 1] = cat[now];
dfs(now + 1, cnt + 1);
cab[cnt + 1] = 0;
}
int main() {
cin >> n >> w;
for (int i = 1; i <= n; i++) {
cin >> cat[i];
}
sort(cat + 1, cat + 1 + n, cmp);
ans = n;
dfs(1, 0);
cout << ans << endl;
return 0;
}
其实可以直接dfs(1,1)
写的好呀，谢谢楼主
%%%
%%%
%%%
%%%
%%%
其实可以直接return cnt，将函数改为int类型，然后直接cout << dfs(1, 0)
为什么上一题用这种方法不用恢复现场啊？
#include [HTML_REMOVED]
using namespace std;
int g[15],a[15],res=15,n;
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
void dfs(int pos,int cnt){ //pos 是枚举到的数的位置，cnt是有几组
if(cnt>res) return;
if(pos==n+1){
res=cnt;
return;
}
for(int i=1;i<=cnt;i){
bool st=1;
for(int j=1;j[HTML_REMOVED]>n;
for(int i=1;i<=n;i) cin>>a[i];
g[1]=1;
dfs(2,1);
cout<<res;
return 0;
}
有时候，直接把dfs参数直接放在函数参数里，然后等函数返回时，原来的数还是没变
为啥要加这一句，加不加不都能过的嘛 cab[cnt + 1] = 0;体现回溯，当然对结果没影响
Louzuyyds
%%%
不是很理解这段代码，虽然知道是新开一辆车，但是为啥就直接写在dfs里，不加个什么判断条件吗不用，因为前面的循环是枚举已经存在的缆车，如果这只猫能在前面放下，早就放进去了，并dfs下一只猫了。只有太重，没有任何缆车要的猫，才只能new一个缆车。条件好的轻猫早就放进去了，只有条件不好的肥猫要new一辆车。
噢噢，懂了，谢谢Orz
大佬求助，为何回溯的时候改写成
cab[cnt + 1] = 0;就会报WA呀，哪怕我回溯不写好像都能AC，为何加了一步反而错了嘞。这个dfs代码应该不是太重没有缆车要的猫才开新车吧，是任何一只猫枚举完所有放入车的可能后，开了一辆车（这也是一种可能）,不加判断条件是为了枚举所有可能。
比如w = 3，猫的重量是1 1 2 2，第一个1进去，第二个1也可以放进去但是让他去开一个新的、让第一个2进去是最优解。而不是让第二个1进去，此时2就进不去了，只能去开一个新的，这就错了。因此不能加判断条件。
这个说，dfs会把所有状态枚举完，开辟一个新车这个会增加很多分支，我们在前面以及枚举出来了最有的答案，就是让胖的猫先进去，后面的情况都亏被if (cnt >= ans) {
return;
}这个条件给剪枝。就是说dfs顺序也会影响时间，所以我们把创建新节点放在最后面。
不是很懂 为什么在开新车的时候还要还原现场 cab［cnt+1］=0
这不就等价于 cab[cnt + 1] -= cat[now];
赞
# 真是神呀
记录美好生活
代码风格好！
%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%
思路非常通俗易懂orz！！
楼楼好棒