问题
翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。
当然，每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？
输入格式
第 1 行：包含两个用空格隔开的整数，N 和 W。
第 2…N+1 行：每行一个整数，其中第 i+1 行的整数表示第 ii 只小猫的重量 Ci。
输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
数据范围
1≤N≤18,
1≤Ci≤W≤
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2
思路
- dfs+剪枝+回溯
遍历每只小猫，记录当前已经使用的缆车数量cnt，以及装载了小猫的缆车重量weight[1]-weight[cnt]。将每个小猫放到当前使用的缆车中加上此小猫后仍没有超重的缆车中，增加缆车的重量，递归下一只小猫的重量，此外，本只小猫也可以新开一个缆车装载，cnt+1，递归下一只小猫。注意，再下一层递归完成后，需要转态回复（回溯）。
在本题中，使用的缆车数量由数据范围可以知道不超过18，则可以当使用的缆车数量大于等于当前的最优解res的时候，结束递归，即剪枝，减少非必要的计算。
题解
#include<iostream>
using namespace std;
int res=20,n,w,c[20],weight[20];
void dfs(int k, int cnt) {
if(cnt >= res) return; //剪枝
if(k == n+1) {
res = min(res,cnt);
return;
}
for(int i=1; i<=cnt; i++) { //之前的缆车
if(c[k]+weight[i]<=w) { //没有超重
weight[i] += c[k];
dfs(k+1,cnt);
weight[i] -= c[k];
}
}
//新开一个缆车
weight[cnt+1] = c[k];
dfs(k+1, cnt+1);
weight[cnt+1] = 0;
}
int main() {
cin>>n>>w;
for(int i=0; i<n; i++) cin>>c[i+1];
dfs(1, 0);
cout<<res<<endl;
return 0;
}
| 标题： | AcWing-165-小猫爬山 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/71 |
| 更新： | 2022-09-18 22:36:25 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |