dfs的练习,先考虑dfs的做题步骤
dfs无非不就是深搜,往深处搜。
需要考虑的问题有:
1.搜索顺序。
2.dfs函数的参数设置。
有关剪枝
1.当遍历这条树枝比之前的还要长那么,不需要再进行深搜了,直接return,当全部元素已经更新完成了,那么长度也更新成最短的。
2.优先考虑决策少的元素.
看题解:
dfs的题目,首先考虑顺序,和函数设置的参数。
参数设置为遍历到了第几只猫,和当前已经用了几辆车。
顺序是从猫的体重从大到小依次遍历。因为猫的体重越小选择越多决策越多,所以我们要从大到小。(剪枝二)
每次都含有两种情况,可以加在之前的车上,和重新开一辆车。
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int x[20],cat[20];
int ans,n,m;
void dfs(int u,int k) {
if(k>=ans) //剪枝
return ;
if( u==n )
{
ans=k; //更新最浅的答案。
return ;
}
for(int i=0;i<k;i++)
{
if(cat[u]+x[i]<=m)
{
x[i]+=cat[u];
dfs(u+1,k);
x[i]-=cat[u];
}
}
x[k]=cat[u];
dfs(u+1,k+1);
x[k]=0;
}
int main() {
scanf("%d%d",&n,&m);
ans=n; //最小答案。
for(int i=0; i<n; i++) scanf("%d",&cat[i]);
sort(x,x+n);//排序
reverse(x,x+n); //倒序,从大到小
dfs(0,0); //0只猫,0辆车。
cout<<ans<<endl;
return 0;
}