DFS搜索之剪枝

AcWing 165. 小猫爬山

题目链接：https://www.acwing.com/problem/content/167/

思路

本题有两个可以剪枝的地方：

• 如果当前的答案已经大于了我们已知的最小答案,不用说直接return返回即可
• 可以将小猫的体重从大到小排序,这样我们的搜索树就会缩短许多，因为我们的剩余空间就变小了,然后可选择的猫也就少了.

代码

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define sc scanf
#define pr printf

const int N=20;
int c[N];
int n,w;
int ans=N;
int sum[N];

void dfs(int u,int k)
{
    //最优性剪枝
    if(k>=ans) return ;
    if(u>n)
    {
        ans=k;
        return;
    }
    //尝试分配到已拥有的缆车上面
    for(int i=0;i<k;i++)
    {
        if(sum[i]+c[u]<=w)//可行性剪枝
        {
            sum[i]+=c[u];
            dfs(u+1,k);
            sum[i]-=c[u];
        }
    }
    //放入一辆新的车
    sum[k]=c[u];
    dfs(u+1,k+1);
    sum[k]=0;
}


int main()
{
    cin>>n>>w;
    for(int i=1;i<=n;i++) cin>>c[i];
    sort(c+1,c+1+n);
    reverse(c+1,c+1+n);
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}