P10483 小猫爬山

· · 题解

P10483 小猫爬山

背景

这是一道 DFS 是个人就能看出来
而我第一种方法没有过（ 哭死 ）结果把DFS的对象改一下就过了
本题与 U208362 分为互质组 方法相同

分析题目

题目要求就是最少需要多少缆车才能装完所有小猫，因此小猫的重量可以少于缆车的载重，但不能大于（意思就是不能把小猫劈开！猫猫这么可爱，这么能劈开呢？）

思路&实现

这道题我们用 DFS 来遍历每一只小猫的重量：

dfs(st,num) $num$是指当前缆车的总数 **每到一只新的小猫，就会面临两个选择：** 1. 把小猫放到一个全新得缆车中，并将缆车的个数加一，且进行下一轮 $DFS
  1. 不选择放入新的缆车，而是在前面已有的缆车中找可以放下的，将他加入，并进行下一轮 DFS

因此我们需要一个sum[i]来储存第 i 辆缆车剩余的容量

结束：

1.当当前遍历的 st==n+1 及遍历完所有小猫，就可以将 ans=num 并返回
2.若你当前的缆车数量已经超过之前的答案及 num>=ans 那就直接返回

最后直接上代码：

#include<bits/stdc++.h>
using namespace std;
int a[20],sum[20];
int n,w;
bool b[20];
int ans=2e9;
void dfs(int st,int num){
    if (num>=ans)
        return;
    if(st==n+1){
        ans=num;
        return;
    }
    sum[num+1]=w-a[st];
    dfs(st+1,num+1); 
    for(int i=1;i<=num;i++) {
        if (sum[i]-a[st]>=0) {
            sum[i]-=a[st];
            dfs(st+1,num);
            sum[i]+=a[st];
        }
    }
}
bool cmp(int x,int y){
    return x>y;
}
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }   
    sort(a+1,a+1+n,cmp);
    dfs(1,0);
    cout<<ans;
    return 0;
}