《算法竞赛进阶指南》165 小猫爬山题解

本文主要是介绍《算法竞赛进阶指南》165 小猫爬山题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考内容：

[洛谷][noip][算法竞赛进阶指南]小猫爬山

《算法竞赛进阶指南》小猫爬山

小猫爬山

题目描述

题目链接：https://www.acwing.com/problem/content/167/

​Freda 和 Rainbow 饲养了 N 只小猫。这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

Freda 和 Rainbow 只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是C₁、C₂……C_n。当然，每辆缆车上的小猫的重量之和不能超过 W。每租用一辆缆车，Freda 和 Rainbow 就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？

输入格式

​第一行包含两个用空格隔开的整数，N 和 W。接下来 N 行每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 C_i。

输出格式

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

分析解答

贪心

经过思考发现，我们只需要尽可能的在每辆车上都放更多的小猫，就能以最经济的方式把所有小猫都送下山。所以是一个非常明显的贪心题目，我们将所有小猫按重量排序，尽可能把肥猫先送下山即可。具体实现代码如下：

#include<bits/stdc++.h>
using namespace std;void cin_arr(int *num, int len)
{for(int i = 0; i < len; i++){cin>>num[i];}
}int slove(int *num, int n, int w)
{int ans = 0;int remain = 0;int load = 0;sort(num, num+n);while(true){for(int i = 0; i < n; i++){// 连当前最小的猫都装不下，那么就新开一辆车if(num[i] != -1 && remain < num[i]){ans++;remain = w;break;}}for(int i = n-1; i >= 0; i--){// 从大到小查找，尽可能装肥猫if(num[i] != -1 && remain >= num[i]){remain -= num[i];// 运送走的小猫重量以 -1 表示num[i] = -1;load++;break;}}// 如果所有小猫都运走了，那么当前 ans 就是答案if(load >= n)return ans;}
}int main()
{int n, w;int cat[1000000];cin>>n>>w;cin_arr(cat, n);cout<<slove(cat, n, w)<<endl;
}

经过实际测试发现，盲目使用贪心思想的算法并不正确，例如如下测试用例。

6 16
9 5 5 5 4 3

贪心的结果是使用 3 辆车，分别为9+5、5+5+4、3；而正确的结果却是使用 2 辆车，分别为9+4+3和5+5+5。

深度优先搜索

既然贪心思想在这里行不通，那么我们就采用暴力搜索，即小猫可以放在现有任意一辆车上。具体实现代码如下：

#include<bits/stdc++.h>
using namespace std;#define N 2000int n, w;
int cat[N];
int sum[N] = {0}; // 第 i 辆车当前重量
int ans = N;void cin_arr(int *num, int len)
{for(int i = 0; i < len; i++){cin>>num[i];}
}void dfs(int cur_cat, int cur_car)
{if(cur_car > ans) // 求最小值，不符合直接返回return ;if(cur_cat == n) { // 所有小猫都上车了ans = cur_car;return ;}for(int i = 0; i < cur_car; i++) {if(sum[i] + cat[cur_cat] <= w) { // 当前猫能放进去sum[i] += cat[cur_cat]; // 当前猫占用重量dfs(cur_cat+1, cur_car); // 继续放下一只猫sum[i] -= cat[cur_cat]; // 把已经放进去的猫拿出来，因为是循环，所以放入下一辆车里面}}// 新开一辆车，把当前这只猫放到新的车里面sum[cur_car] = cat[cur_cat];dfs(cur_cat+1, cur_car+1);sum[cur_car] = 0; // 把猫拿出来
}int main()
{cin>>n>>w;cin_arr(cat, n);dfs(0, 0);cout<<ans<<endl;
}

搜索优化

考虑到每次都是在车数量固定的情况下进行搜索的，那么少满足一次(sum[i] + cat[cur_cat] <= w)条件，就会少一次递归的调用，也即少一次搜索。那么如何能尽快使得程序尽快不满足该条件呢？

让sum[i]减小的速度加快就会减少搜索分支，即每次放更重一点的猫进去，就能达到效果。所以我们可以在进行搜索前将小猫的重量进行降序排序，这样从肥猫开始搜索就会减少分支。

#include<bits/stdc++.h>
using namespace std;#define N 2000int n, w;
int cat[N];
int sum[N] = {0}; // 第 i 辆车当前重量
int ans = N;void cin_arr(int *num, int len)
{for(int i = 0; i < len; i++){cin>>num[i];}
}bool cmp(int a, int b)
{return a > b;
}void dfs(int cur_cat, int cur_car)
{if(cur_car > ans) // 求最小值，不符合直接返回return ;if(cur_cat == n) { // 所有小猫都上车了ans = cur_car;return ;}for(int i = 0; i < cur_car; i++) {if(sum[i] + cat[cur_cat] <= w) { // 当前猫能放进去sum[i] += cat[cur_cat]; // 当前猫占用重量dfs(cur_cat+1, cur_car); // 继续放下一只猫sum[i] -= cat[cur_cat]; // 把已经放进去的猫拿出来，因为是循环，所以放入下一辆车里面}}// 新开一辆车，把当前这只猫放到新的车里面sum[cur_car] = cat[cur_cat];dfs(cur_cat+1, cur_car+1);sum[cur_car] = 0; // 把猫拿出来
}int main()
{cin>>n>>w;cin_arr(cat, n);sort(cat, cat+n, cmp); // 反排序优化搜索dfs(0, 0);cout<<ans<<endl;
}

这篇关于《算法竞赛进阶指南》165 小猫爬山题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---