【解题报告】 小猫爬山
解题思路：
哪家会养这么重又这么多猫，只能说他们两个比较闲的无聊
当然这道题就像猫一样，特别狡猾
开始的时候我看到这个，想到了一个贪心做法，但是不管怎么改，答案就是改不对，经过前思后想，左顾右盼，我知道了真正的算法：搜索+剪枝
恰好就是我不最擅长的算法！
我就按照思路和书中所给的部分代码打出来了，当我提交上去的时候，一个大大的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;
}
|
