题解：P10483 小猫爬山

cyhyeee · 2024-04-20 16:46:15 · 题解

题解：P10483 小猫爬山

题目传送门

来简单分析下题意：N 只猫的重量，最大承重量为 W 的缆车，求最少用多少个缆车才能全部装起来。

设最大承重量为 limit，所以我们要先按从大到小排序，选定一只猫后，在 dfs，用剩下的猫来补缝隙，直到无法补。用一个 sum 数组来表示 i 号缆车现在的重量，w 来表示每只猫的重量，k 表示当前开了几个缆车。如果当前车厢加上这只猫的重量不超过 limit 则 sum_i \gets sum_i +w_i。结束后将 sum_k = w_u，再 dfs 下一层，dfs 之后还原 sum，即 sum_u = 0。

code：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20;
int w[N], sum[N];
int n, limit, ans;
void dfs(int u, int k){
    if (k >= ans) return;//剪枝。
    if (u == n) ans = k;//小猫都装完了，更新答案。
    for (int i = 0; i < k; i++){
        if (sum[i] + w[u] <= limit){
            sum[i] += w[u];
            dfs(u + 1, k);
            sum[i] -= w[u];
        }
    }
    sum[k] = w[u];
    dfs(u + 1, k + 1);//再开一个缆车，同时当前这只小猫已经固定在这个缆车里了，所以是u+1。
    sum[k]=0;
}
int main(){
    cin >> n >> limit;
    ans = n;
    for (int i = 0; i < n; i++){
        cin >> w[i];
    }
    sort(w, w + n, greater<int>());
    dfs(0, 0);
    cout << ans;
    return 0;
}