小猫爬山

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

还记得一次教练将它的名字改了拿来比赛

题目

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

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

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

思路

这题肯定是深搜啊，不要想了，大胆去写吧！

等等好像有点不对！我闻到了TLE的味道，不如我们将它加点小小的（砍树）剪枝技巧吧。

  1. 优化搜索顺序：将小猫由重到轻排序，先重的小猫坐上缆车。
  2. 最优性剪枝：如果当前搜索到的结果比我之前找到的答案还大的话就直接return，不需要再搜索下去了。

加了这两个剪枝后，TLE就不会出现在你的眼前了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int n,w,a[51],ans,x[51];
bool cmp( int x,int y){ return x>y; }//压行了解一下
void dfs(int now,int cnt){//搜索正文
//两个参数，一个是now，第几只小猫；一个是cnt，用了几辆缆车。
	if(cnt>ans) return;//最优性剪枝
	if(now>n){//此时所有小猫都已安排好了
		ans=cnt;return;//更新答案并返回，不能再搜下去了
	}
	for(int i=1;i<=cnt;i++)
	if(x[i]+a[now]<=w){//如果之前的缆车还可以将这只可怜的小猫装下的话
		x[i]+=a[now]; dfs(now+1,cnt); x[i]-=a[now];//记录并接着搜索，不要忘记回溯
	}
	x[cnt+1]=a[now]; dfs(now+1,cnt+1); x[cnt+1]=0;//VIP享受，单猫再来一缆车
}
int main(){
	cin>>n>>w;//输入
	ans=n;//最坏时一只猫一缆车
	for(int i=1;i<=n;i++)
	cin>>a[i];
	sort(a+1,a+1+n,cmp);//由大到小排序，快排方便又轻松，再也不用担心TLE了
	dfs(1,0);
	cout<<ans<<endl;//简单输出
	return 0;
}

这题不难，但我想知道为什么我之前由小到大排，从后往前搜时TLE了，求各位路过大佬教一下。

88~~~

Thanks for your coming.

（小秘密）