UVa 10715 Cat

原创于 2025-12-13 12:13:29 发布 · 921 阅读

13 ·

CC 4.0 BY-SA版权

文章标签：

#算法 #c++ #青少年编程

动态规划专栏收录该内容

147 篇文章

订阅专栏

题目描述

在强风中，帆船会向背风侧倾斜，这会导致两个问题：有效帆面积减小（从而降低速度）和可能倾覆的风险。双体船通过将船体分为左右两部分来增加有效宽度，减少倾斜。此外，船员可以通过调整位置和使用压舱物来进一步平衡船只。

本题中，船长决定使用 $n$ 块石头作为压舱物，需要将它们分配到左舷和右舷船体中，使得两舷的总重量差不超过 $2%2\%$ 。给定每块石头的重量（正实数，不超过 $100$ ），要求输出放入右舷的石头编号（其余放入左舷）。如果有多个解，输出任意一个即可。题目保证存在满足条件的解。

输入格式 ：多组测试用例，每组以整数 $n$ （ $\leq 100$ ）开始，随后 $n$ 行每行一个实数表示石头重量。输入以 $0$ 结束。

输出格式 ：对于每组测试用例，输出一行，包含应放入右舷的石头编号，编号之间用空格隔开。

样例输入 ：

样例输出 ：

3 5

题目分析与解题思路

问题本质

这是一个子集和问题的变体：我们需要从 $n$ 个物品（石头）中选出一个子集（放入右舷），使得子集的总重量尽可能接近所有石头总重量的一半，且允许的相对误差不超过 $2%2\%$ 。设总重量为 $W$ ，则目标重量 $t a r g e t = W /2$ ，允许的绝对误差为 $\times 0.02$ 。我们需要找到一个子集，其重量 $s u m$ 满足 $\leq W \times 0.02$ 。

直接枚举的不可行性

最直接的方法是枚举所有可能的子集（ $2^n$ 个），但 $n$ 最大为 $100$ ， $2^{100}$ 的枚举量是完全不可接受的。因此，我们需要一种更高效的算法。

动态规划思路

由于重量是实数，直接作为动态规划的状态维度会带来精度问题。一个常见的技巧是将实数重量转换为整数，从而可以使用整数动态规划。转换的关键在于选择一个合适的放大倍数，使得转换后的整数能够精确表示原始重量，同时保证舍入误差在允许范围内。

放大倍数的选择

题目中重量是正实数，不超过 $100$ ，但最小可能非常小（例如 $0.001$ ）。为了确保精度，我们需要让放大后的最小重量足够大。设最小重量为 $minW e i g h t$ ，我们选择放大倍数 $\lceil 1000.0 / minWeight \rceil$ 。这样，放大后的最小重量至少为 $1000$ ，有效避免了舍入误差累积导致解不满足 $2%2\%$ 误差要求的问题。

整数动态规划

将每个石头的重量乘以 $sc a l e$ 后四舍五入得到整数重量 $in t W e i g h t [i]$ 。设总重量放大后为 $t o t a l I n t$ ，目标值为 $t a r g e t I n t = t o t a l I n t /2$ ，允许的绝对误差为 $\times scale \times 0.02)$ 。

我们定义 $d p [s u m]$ 表示是否存在一个子集，其放大后的总重量恰好为 $s u m$ 。同时，为了能够回溯得到具体的石头编号，我们还需要记录 $p re v [s u m]$ ，表示达到重量 $s u m$ 时最后加入的石头的编号（ $1-based\texttt{1-based}$ ）；若 $p re v [s u m] = 0$ 则表示没有石头加入或该状态不可达。

动态规划的过程是一个标准的 $0/1\texttt{0/1}$ 背包 ：

初始化 $d p [0] = t r u e$ ， $p re v [0] = 0$ 。
对于每块石头 $i$ （重量 $in t W e i g h t [i]$ ），从大到小遍历 $s u m$ （避免同一块石头被重复使用）：
- 如果 $d p [s u m]$ 为真且 $d p [s u m + in t W e i g h t [i]]$ 为假，则更新 $d p [s u m + in t W e i g h t [i]] = t r u e$ ，并记录 $p re v [s u m + in t W e i g h t [i]] = i + 1$ 。

动态规划结束后，我们在区间 $[t a r g e t I n t - a ll o w e d D i ff I n t, t a r g e t I n t + a ll o w e d D i ff I n t]$ 内寻找一个可达的 $s u m$ （即 $d p [s u m] = t r u e$ ）。由于题目保证解存在，我们总能找到这样的 $s u m$ 。

回溯构造解

从找到的 $b es tS u m$ 开始，利用 $p re v$ 数组回溯：

若 $\neq 0$ ，则将该石头编号加入结果集合，然后令 $b es tS u m$ 减去该石头的整数重量，继续回溯。
重复直到 $b es tS u m = 0$ 。

回溯得到的石头编号即为放入右舷的石头。最后，将编号按升序排序输出即可。

算法复杂度分析

时间复杂度 ：动态规划部分需要遍历每块石头和所有可能的重量和。放大后的总重量 $t o t a l I n t$ 最大约为 $100 \times 100 \times scale$ ，在最坏情况下 $sc a l e$ 可能较大，但实际测试中 $sc a l e$ 不会过于夸张。整体复杂度为 $\times totalInt)$ ，在题目限制下是可接受的。
空间复杂度 ：主要消耗在于 $d p$ 和 $p re v$ 数组，大小为 $O (t o t a l I n t)$ 。同样在题目限制下可行。

为什么贪心算法不行？

简单的贪心策略（例如将石头按重量排序后，依次放入当前总重量较小的一侧）虽然易于实现，但不能保证总是满足 $2%2\%$ 的误差要求。题目只要求误差不超过 $2%2\%$ ，但贪心可能在某些刁钻的数据下产生更大的误差。因此，为了保证正确性，我们必须使用能够精确搜索接近目标值的动态规划方法。

代码实现

// Cat
// UVa ID: 10715
// Verdict: Accepted
// Submission Date: 2025-12-13
// UVa Run Time: 0.830s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while (cin >> n, n != 0) {
        vector<double> weights(n);
        double minWeight = 1000.0;  // 初始化一个较大的值，用于记录最小重量
        double totalWeight = 0.0;

        // 读入重量并计算总重量和最小重量
        for (int i = 0; i < n; ++i) {
            cin >> weights[i];
            totalWeight += weights[i];
            if (weights[i] < minWeight) minWeight = weights[i];
        }

        // 动态计算放大倍数，确保最小重量放大后至少为 1000
        double scale = ceil(1000.0 / minWeight);
        
        // 将重量转换为整数
        vector<int> intWeights(n);
        for (int i = 0; i < n; ++i) {
            intWeights[i] = int(round(weights[i] * scale));
        }

        int totalInt = round(totalWeight * scale);
        int targetInt = totalInt / 2;
        int allowedDiffInt = round(totalWeight * scale * 0.02);  // 2% 误差对应的整数值

        // 动态规划：dp[sum] 表示是否存在子集和为 sum，prev[sum] 记录最后一块石头编号
        vector<bool> dp(totalInt + 1, false);
        vector<int> prev(totalInt + 1, 0);
        dp[0] = true;

        // 0/1背包动态规划
        for (int i = 0; i < n; ++i) {
            for (int s = totalInt - intWeights[i]; s >= 0; --s) {
                if (dp[s] && !dp[s + intWeights[i]]) {
                    dp[s + intWeights[i]] = true;
                    prev[s + intWeights[i]] = i + 1;  // 记录石头编号（1-based）
                }
            }
        }

        // 寻找最接近 targetInt 且误差在允许范围内的子集和
        int bestSum = 0;
        for (int s = targetInt; s <= totalInt; ++s) {
            if (dp[s] && abs(s - targetInt) <= allowedDiffInt) {
                bestSum = s;
                break;
            }
        }
        if (bestSum == 0) {
            for (int s = targetInt; s >= 0; --s) {
                if (dp[s] && abs(s - targetInt) <= allowedDiffInt) {
                    bestSum = s;
                    break;
                }
            }
        }

        // 回溯得到右舷石头编号
        vector<int> result;
        int cur = bestSum;
        while (cur > 0) {
            int rockId = prev[cur];
            result.push_back(rockId);
            cur -= intWeights[rockId - 1];  // 重量数组索引是 0-based
        }

        // 输出结果（按升序排序）
        sort(result.begin(), result.end());
        for (size_t i = 0; i < result.size(); ++i) {
            if (i > 0) cout << " ";
            cout << result[i];
        }
        cout << "\n";
    }

    return 0;
}

总结

本题的关键在于将实数重量的子集和问题通过合适的放大倍数转换为整数动态规划问题。通过精心选择放大倍数，我们能够在保证精度的前提下，利用高效的 0/1 背包算法找到满足误差要求的解。动态规划结合回溯的方法确保了我们可以输出具体的石头编号，而不仅仅是判断是否存在解。这道题综合了数值处理、动态规划和回溯构造，是一道很好的练习题目。