小猫爬山 DFS

245 阅读 3 评论 0 点赞

题目描述
翰翰和达达饲养了N只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN
当然，每辆缆车上的小猫的重量之和不能超过W。
每租用一辆缆车，翰翰和达达就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？

输入格式
第1行：包含两个用空格隔开的整数，N和W。
第2..N+1行：每行一个整数，其中第i+1行的整数表示第i只小猫的重量Ci。

输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
数据范围
1≤N≤18
1≤Ci≤W≤108
    #include<bits/stdc++.h>
    using namespace std;
    
    const int N=20;
    int a[N],sum[N];//a 小猫重量 sum 车现载重
    int n,w;
    int res;
    
    void dfs(int u,int cnt)//u 当前第几只猫，cnt当前车的数量
    {
        if(cnt>=res)return ;//如果车的数量大于现实存在的猫咪的个数，或者历史最优的数值，返回
        if(u==n){res=cnt;return ;}//如果考虑完了n只即所有猫咪，则更新答案
        for(int i=0;i<cnt;i++)
            if(sum[i]+a[u]<=w)//检查现有的所有车的重量，是否能放猫
                {
                    sum[i]+=a[u];
                    dfs(u+1,cnt);
                    sum[i]-=a[u];
                }
        sum[cnt]=a[u];//新增一辆车，初始重量是当前猫的重量
        dfs(u+1,cnt+1);
        sum[cnt]=0;
    }
    
    int main()
    {
        cin>>n>>w;
        res = n;
        
        for(int i=0;i<n;i++)cin>>a[i];
        
        sort(a,a+n,[](int a,int b){return a>b;});//反序排序 
        dfs(0,0);
        cout<<res;
        return 0;
    }
    
    
- 在这段代码中，sum[i] -= a[u]; 这一行是深度优先搜索（DFS）算法中的一个关键步骤，它的作用是进行回溯。
在DFS中，我们尝试不同的路径来寻找问题的解。当我们进入一个递归调用时，我们会做出一些选择（比如将当前的小猫a[u]放入某辆车中），然后继续搜索。当我们完成这个选择下的所有可能的搜索后，我们需要撤销这个选择，以便回到上一个状态，尝试其他可能的选择。这个过程就是回溯。
具体到这段代码中：
sum[i] += a[u];：当我们尝试将第u只小猫放入第i辆车时，我们将这只小猫的重量加到这辆车的当前载重sum[i]上。
dfs(u+1, cnt);：递归调用dfs函数，尝试放入下一只小猫。
sum[i] -= a[u];：在递归调用返回后，我们需要撤销之前将小猫放入车辆的操作，以便这辆车可以被用于其他小猫。这就是回溯的步骤，我们将小猫的重量从sum[i]中减去，恢复到放入小猫之前的状态。

- 在这段代码中，sum[cnt] = 0; 这一行的作用是在尝试将当前小猫放入新车辆后，恢复车辆载重数组sum的状态，以便可以重新使用这辆车。
具体来说，代码中的这一部分：
    sum[cnt] = a[u]; // 新增一辆车，初始重量是当前猫的重量
    dfs(u+1, cnt + 1); // 递归调用dfs，尝试放入下一只小猫
	sum[cnt] = 0; // 回溯，恢复车辆载重为0

sum[cnt] = a[u];：这一行将当前小猫a[u]的重量赋值给sum[cnt]，表示我们尝试将这只小猫放入一个新的车辆（即第cnt辆车），这个新车辆的初始载重就是这只小猫的重量。
dfs(u+1, cnt + 1);：递归调用dfs函数，尝试放入下一只小猫。此时，我们已经假设第u只小猫已经被放入了第cnt辆车，并且我们正在尝试放入下一只小猫。
sum[cnt] = 0;：在递归调用返回后，我们需要撤销之前将小猫放入新车辆的操作。这是因为我们需要回到上一个状态，以便这辆车可以被用于其他小猫，或者被完全空出来。因此，我们将sum[cnt]重置为0，表示这辆车现在是空的，没有载重。

0.0分

1 人评分

本文分类：文章列表
浏览次数：245 次浏览
发布日期：2024-11-22 17:47:34
本文链接：https://blog.dotcpp.com/a/107364

上一篇 > 2222222222222222222222222222222222222222222222
下一篇 > 题目 1034: [编程入门]自定义函数之数字分离

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 3 条评论

十五月明 1月前回复TA

这个顺序确保了我们尝试了所有可能的放置方案：

我们首先尝试将小猫放入已有的任何一辆车中。
如果所有已有车辆都无法放入当前小猫，我们才尝试新增一辆车。

十五月明 1月前回复TA

@十五月明 这个顺序确保了我们尝试了所有可能的放置方案：  我们首先尝试将小猫放入已有的任何一辆车中。 如果所有已有车辆都无法放入当前小猫，我们才尝试新增一辆车。

十五月明 1月前回复TA

为什么是先for (int i = 0; i < cnt; i++)完全遍历，之后才
    sum[cnt] = a[u]; // 新增一辆车，初始重量是当前猫的重量
    dfs(u + 1, cnt + 1);
    sum[cnt] = 0;

    这个顺序是为了尝试所有可能的放置小猫的方案，并找到需要的最少车辆数。这个顺序反映了深度优先搜索（DFS）算法的回溯特性。下面是代码逻辑的详细解释：
遍历所有已有车辆：
for (int i = 0; i < cnt; i++) 这个循环遍历所有已有的车辆（即cnt辆车）。对于每一辆车，我们检查是否可以将当前的小猫（第u只小猫）放入这辆车中，而不超出车辆的最大载重量w。

如果可以放入，我们将小猫的重量加到这辆车的当前载重sum[i]上，然后递归调用dfs(u+1, cnt)，尝试放入下一只小猫。
递归返回后，我们需要撤销这个操作（回溯），所以我们将小猫的重量从sum[i]中减去，恢复到原来的状态。
尝试新增一辆车：
在尝试了所有已有车辆后，我们再尝试新增一辆车来放置当前的小猫。这是通过sum[cnt] = a[u];实现的，我们将当前小猫的重量作为新增车辆的初始载重。

然后，我们递归调用dfs(u+1, cnt+1)，尝试放入下一只小猫，同时使用新增的这辆车。
递归返回后，我们再次回溯，将新增车辆的载重sum[cnt

小猫爬山 DFS

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 3 条评论

发表评论 取消回复

评论列表共有 3 条评论

发表评论取消回复