小猫爬山｜MGblog

题目：小猫爬山

题目描述：
翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了。翰翰和达达只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C_1, C_2, \dots, C_N。每辆缆车上的小猫的重量之和不能超过 W。每租用一辆缆车，翰翰和达达就要付 1 美元，求最少需要多少美元才能把这 N 只小猫都运送下山。

输入描述：

第 1 行：两个用空格隔开的整数 N 和 W。
第 2 行到第 N+1 行：每行一个整数，表示每只小猫的重量 C_i。

输出描述：
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

样例输入：

样例输出：

提示：
1 \leq N \leq 18, 1 \leq C_i \leq W \leq 10^8

思路：DFS

DFS 函数部分：void dfs(int x, int k)，其中 x 表示当前处理的小猫编号，k 表示当前已经使用的缆车数量。
- 如果当前使用的缆车数量 k 已经大于等于 minn（当前最小所需美元数），则返回（进行剪枝，提高效率）。
- 如果已经处理完所有小猫，更新 minn 为当前所需缆车数量 k，并返回。
- 尝试将当前小猫放入当前缆车，并递归调用 dfs 函数继续处理下一只小猫，处理完后将该小猫从当前缆车中移除。
- 尝试将当前小猫单独放入一辆新的缆车，并递归调用 dfs 函数继续处理下一只小猫，处理完后将该小猫从当前缆车中移除。
主函数部分：
- 排序：将小猫的重量按照从大到小排序，以便先处理重的小猫。
- 调用 DFS：调用 dfs 函数从第一只小猫开始进行深度优先搜索，初始已用缆车数量为 0。
- 输出结果：输出计算得到的最少所需美元数。

AC代码：

#include<bits/stdc++.h>
#define N 1001
using namespace std;
int w, n, car[N], cat[N], minn = 0x3f3f3f3f;
bool cmp(int x, int y) { return x > y; }

void dfs(int x, int k) {
    if (k >= minn) return;
    if (x == n + 1) {
        minn = min(minn, k);
        return;
    }
    for (int i = 1; i <= k; i++) {
        if (car[i] + cat[x] <= w) {
            car[i] += cat[x];
            dfs(x + 1, k);
            car[i] -= cat[x];
        }
    }
    car[k + 1] += cat[x];
    dfs(x + 1, k + 1);
    car[k + 1] -= cat[x];
}

int main() {
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> cat[i];
    }
    sort(cat + 1, cat + 1 + n, cmp);
    dfs(1, 0);
    cout << minn;
    return 0;
}

时间复杂度: O(n!)
空间复杂度: O(n)

其他方法：状态压缩DP

将猫的数量设成二进制数（最多有 10 只）。
f[i][j] 中 i 是缆车数量，j 是当前已选择的小猫集合的状态。
动态转移方程：若当前猫能被放入缆车，则更新状态；否则，新开一辆缆车，状态转移。
最终输出最少缆车数。

AC代码：

#include<bits/stdc++.h>
#define N 1000001
using namespace std;
int n, W, w[N], f[20][N], ans = 0x3f3f3f3f;

int main() {
    cin >> n >> W;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    f[1][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= (1 << n) - 1; j++) {
            if (f[i][j] != 0x3f3f3f3f) {
                for (int k = 1; k <= n; k++) {
                    if ((j | (1 << (k - 1))) != j && f[i][j] + w[k] <= W) {
                        f[i][j | (1 << (k - 1))] = min(f[i][j | (1 << (k - 1))], f[i][j] + w[k]);
                    } else {
                        f[i + 1][j | (1 << (k - 1))] = min(f[i + 1][j | (1 << (k - 1))], w[k]);
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (f[i][(1 << n) - 1] != 0x3f3f3f3f) {
            ans = min(ans, i);
        }
    }
    cout << ans;
    return 0;
}

小猫爬山

题目：小猫爬山

热门文章