B22 DFS剪枝 小猫爬山

#include<bits/stdc++.h>//by:hansang
using namespace std;
bool cmp(int a1, int a2){return a1>a2;}//按照重量递减排序，时间更快 
int n, W, ans, c[20], a[20];//c[i]表示第i辆缆车的重量 
void dfs(int x, int s)//x表示当前轮到第x只小猫，s表示当前用了s辆缆车 
{
    if(ans<=s) return ;//剪枝（已选缆车大于答案） 
    if(x==n+1)
    {
        ans=min(ans,s);
        return ;
    }
    for(int i=1;i<=s;i++)//在已选缆车里放猫 
    {
        if(c[i]+a[x]<=W)//能放得下 
        {
            c[i]+=a[x];//放下 
            dfs(x+1,s);
            c[i]-=a[x];//回溯（拿出来） 
        }
    }
    c[s+1]=a[x];
    dfs(x+1,s+1);//在新缆车里放猫 
    c[s+1]=0;
}
int main()
{
    memset(c,0,sizeof(c));//重量清零 
    scanf("%d%d",&n,&W);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1,cmp);
    ans=n+1;dfs(1,0);//ans赋值n+1辆缆车，递归当前第一只猫，零辆缆车 
    printf("%d\n",ans);
    return 0;
}

B22 DFS剪枝 小猫爬山

#include<bits/stdc++.h>//by:hansang
using namespace std;
bool cmp(int a1,int a2){return a1>a2;}//按照重量递减排序，时间更快 
int n,W,ans,c[20],a[20];//c[i]表示第i辆缆车的重量 
void dfs(int x,int s)//x表示当前轮到第x只小猫，s表示当前用了s辆缆车 
{
    if(ans<=s) return ;//剪枝（已选缆车大于答案） 
    if(x==n+1)
    {
        ans=min(ans,s);
        return ;
    }
    for(int i=1;i<=s;i++)//在已选缆车里放猫 
    {
        if(c[i]+a[x]<=W)//能放得下 
        {
            c[i]+=a[x];//放下 
            dfs(x+1,s);
            c[i]-=a[x];//回溯（拿出来） 
        }
    }
    c[s+1]=a[x];
    dfs(x+1,s+1);//在新缆车里放猫 
    c[s+1]=0;
}
int main()
{
    memset(c,0,sizeof(c));//重量清零 
    scanf("%d%d",&n,&W);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1,cmp);
    ans=n+1;dfs(1,0);//ans赋值n+1辆缆车，递归当前第一只猫，零辆缆车 
    printf("%d\n",ans);
    return 0;
}