【解题报告】 小猫爬山

题目：小猫爬山

解题思路：

哪家会养这么重又这么多猫，只能说他们两个比较闲的无聊

当然这道题就像猫一样，特别狡猾

开始的时候我看到这个，想到了一个贪心做法，但是不管怎么改，答案就是改不对，经过前思后想，左顾右盼，我知道了真正的算法：搜索+剪枝

恰好就是我不最擅长的算法！

我就按照思路和书中所给的部分代码打出来了，当我提交上去的时候，一个大大的A字亮在我的眼前，没错

AC代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int c[20],cab[20],n,w,ans;
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]+c[now]<=w)
		{
			cab[i]+=c[now];
			dfs(now+1,cnt);
			cab[i]-=c[now];
		}
	}
	cab[cnt+1]=c[now];
	dfs(now+1,cnt+1);
	cab[cnt+1]=0;
}
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	cin>>c[i];
	sort(c+1,c+1+n,cmp);
	ans=n;
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}