0-1背包问题（浮点数）

Question

0-1 背包问题，一共 n <= 20 个物品，每个物品价格 p[i] （浮点数），重量 w[i] （浮点数），背包容量 M （浮点数）。求最大能装的价值是多少？

输入：
20 678.91
23.56 51.56
31.45 23.56
62.54 45.62
15.32 42.23
12.32 65.32
65.12 32.45
15.65 45.78
62.15 98.32
32.15 45.62
15.44 95.32
45.65 99.45
32.15 22.48
23.56 51.56
31.45 23.56
62.54 45.62
15.32 42.23
12.32 65.32
65.12 32.45
15.65 45.78
62.15 98.32
输出：
1050.07

1 方法一：转成经典 0-1 背包问题

这个问题和经典 0-1 背包问题很类似，将题目中给的数据都乘 100 将可以转成经典的 0-1 背包问题。

不过转换之后的背包容量为 67891 ，而物品数量为 20，时间复杂度和空间复杂度都较高。

优点：

• 简单，可以复用经典 0-1 背包问题的代码实现。 缺点：
• 浮点到整数转换的倍数需要根据具体问题来选择
  • 可能会导致数据溢出
  • 很容易造成很高的时间和空间复杂度
  • 灵活度较低

/** 0-1背包问题（浮点数）: 转成经典0-1背包问题（整数） TC: O(N*M*100) SC: O(M*100) */
 
int knapsack01(const vector<int>& prices, const vector<int>& weights, int M) {
    int N = prices.size();
    vector<int> dp(M + 1, 0);
    for (int i = 1; i <= N; i++) {
        for (int j = M; j > 0; j--) {
            if (weights[i - 1] <= j) {
                dp[j] = max(dp[j], dp[j - weights[i - 1]] + prices[i - 1]);
            }
        }
    }
    return dp[M];
}
 
float knapsack01_float_to_int(const vector<float>& prices, const vector<float>& weights, float M) {
    int N = prices.size();
    // 将浮点数转换为整数，乘以100（或其他合适的倍数）来避免精度问题
    int multiplier = 100;
 
    vector<int> int_prices(N), int_weights(N);
    for (int i = 0; i < N; ++i) {
        int_prices[i] = static_cast<int>(prices[i] * multiplier + 0.5f); // 四舍五入到整数
        int_weights[i] = static_cast<int>(weights[i] * multiplier + 0.5f);
    }
    return knapsack01(int_prices, int_weights, static_cast<int>(M * multiplier + 0.5f)) / static_cast<float>(multiplier);
}

2 方法二：暴力搜索（回溯法）

暴力搜索的思路是枚举所有可能的物品组合，计算每种组合的总重量和总价值，找到符合背包容量限制的最大价值。

因为 n⇐ 20, 当 n 较大时时间复杂度难以接受。

可以做的一些优化：

• 重量剪枝 ：如果当前背包重量加上已选物品的重量超过背包容量，则不考虑该物品。

要实现暴力搜索，也有几种方法：

2.1 二进制枚举

优点：

• 空间复杂度为 $O(1)$ ，不需要额外的存储空间。
• 无递归，全部用循环，效率略高。
• 不会有栈溢出问题。 缺点：
• 时间复杂度较高为 $O(N\ast 2^N)$ ，尤其当物品数量较多时，计算量会非常大。

Note

这里 $O(N\ast 2^N)$ 中多乘个 N 是因为每种组合需要计算总重量和总价值。

/** 0-1背包问题（浮点数）：二进制枚举 TC: O(N*2^N) SC: O(1)*/
float knapsack01_float_binary_enum(const vector<float>& prices, const vector<float>& weights, float M) {
    int N = prices.size();
    float max_value = 0.f;
    uint32_t total = static_cast<uint32_t>(1) << N; // 用static_cast<uint32_t>(1) << N，避免移位溢出
    for (uint32_t mask = 0; mask < total; ++mask) {
        float current_weight = 0.f, current_value = 0.f;
        for (int i = 0; i < N; ++i) {
            if (mask & (1u << i)) {
                current_weight += weights[i];
                if (current_weight > M) {
                    break; // 剪枝：超重直接跳出
                }
                current_value += prices[i];
            }
        }
        if (current_weight <= M) { // 确保当前重量不超过背包容量
            max_value = max(max_value, current_value);
        }
    }
    return max_value;
}

2.2 递归实现（回溯法、DFS）

优点：

• 剪枝更有效（相比二进制枚举） 缺点：
• 需要额外的递归栈空间，空间复杂度为 $O(N)$ ，其中 $N$ 是物品数量。
• 不适合大规模数据

/** 0-1背包问题（浮点数）：递归回溯 TC: O(2^N) SC: O(N)
 * 由于 M 是 float，无法直接用于哈希或数组下标，不适合常规记忆化（DP）。
 * 若需记忆化，需对 M 离散化（如四舍五入到某一精度），但会引入精度误差。
 */
float _knapsack01_float_recursive_helper(const vector<float>& prices, const vector<float>& weights, float M, int index) {
    if (index < 0 || M <= 0) {
        return 0.f; // 基本情况：没有物品或背包容量为0
    }
    // 不选当前物品
    float max_value = _knapsack01_float_recursive_helper(prices, weights, M, index - 1);
    // 选当前物品（如果不超重）
    if (weights[index] <= M) {
        max_value = max(max_value,
                        prices[index] + _knapsack01_float_recursive_helper(prices, weights, M - weights[index], index - 1));
    }
    return max_value;
}
 
float knapsack01_float_recursive(const vector<float>& prices, const vector<float>& weights, float M) {
    int N = prices.size();
    return _knapsack01_float_recursive_helper(prices, weights, M, N - 1);
}

3 方法三：折半枚举（推荐）

有时候，问题的规模比较大，外面无法枚举所有元素的组合，但能枚举一半或者一部分的组合。此时，将问题拆分成两半或几部分后分别枚举，再合并他们，这一方法往往非常有效。

Note

这属于典型的分治思想！

回到这个问题，当 N 比较大时，$2^N$ 的枚举数量会非常大，可以尝试所有物品分成多个部分，然后对分解的子问题进行合并，分解的部分越多，合并的复杂度也越高。

3.1 代码实现

这里以二分法为例，将问题分成两部分，分别枚举每一部分的所有组合，然后将两部分的组合进行合并。

/** 0-1背包问题（浮点数）：折半枚举 TC: O() SC: O() */
float knapsack01_float_half_enum(const vector<float>& prices, const vector<float>& weights, float M) {
    int N = prices.size(), N1 = N / 2, N2 = N - N1;
    float max_value = 0.f;
 
    // ⭐1: 对 weights 进行排序，按照重量从小到大排列，这样可以：
    // (1) 当组合重量超过 M，可以提前中断整个枚举循环（因为后续的组合重量一定会超过 M）
    // (2) 在枚举组合时，可以丢弃价值比前面低的组合（因为组合是按重量排序的，如果该组合价值比前低，重量却比前面高，是不可能选择的）
    // (3) 省去后续对枚举组合的排序操作
    vector<int> sorted_indices(N);
    std::iota(sorted_indices.begin(), sorted_indices.end(), 0);
    sort(sorted_indices.begin(), sorted_indices.end(), [&](int i, int j) { return weights[i] < weights[j]; });
 
    // 二进制枚举 TC: O((N/2)*2^(N/2))
    auto binary_enum = [&](int left, int right, vector<pair<float, float>>& wp) {
        wp.reserve(1u << (right - left + 1)); // 预留空间，避免频繁扩容
        for (uint32_t mask = 0; mask < (1u << (right - left + 1)); mask++) {
            float weight_sum = 0.f, value_sum = 0.f;
            for (int i = left; i <= right; i++) {
                if (mask & (1u << (i - left))) {
                    weight_sum += weights[sorted_indices[i]];
                    if (weight_sum > M) {
                        break; // 超重，跳出循环
                    }
                    value_sum += prices[sorted_indices[i]];
                }
            }
            if (weight_sum <= M) { // 确保当前重量不超过背包容量
                // ⭐1(2): 丢弃价值比前面低的组合（因为组合是按重量排序的，该组合重量比前面高，价值比前低，是不可能选择的）
                if (wp.empty() || wp.back().second < value_sum) {
                    wp.emplace_back(weight_sum, value_sum);
                }
            } else {
                break; //⭐1(1):提前中断整个枚举循环（因为后续的组合重量一定会超过 M）
            }
        }
        wp.shrink_to_fit(); // 收缩容量，避免浪费空间
    };
 
    // 枚举左右半部分的物品组合方式，丢弃超过背包容量的组合
    vector<pair<float, float>> wp1, wp2;
    binary_enum(0, N1 - 1, wp1);
    binary_enum(N1, N - 1, wp2);
    // ⭐ Note: wp2 本身可以不存储的，只要在遍历右边时合并即可，但会导致一些额外的计算，本质也是空间换时间，这里看如何取舍了
 
    // 合并左右半部分的组合，寻找最优解 TC: O(N log N)
    for (const auto& [w1, v1] : wp1) {
        // ⭐2: 二分法找到重量最接近 M - w1 的组合 TC: O(log N)
        auto it = lower_bound(wp2.begin(), wp2.end(), make_pair(M - w1, 0.f));
        if (it != wp2.begin()) {
            --it;
            max_value = max(max_value, v1 + it->second);
        } else {
            // 如果没有找到合适的组合，说明当前 w1 已经是最大的了
            max_value = max(max_value, v1);
        }
    }
 
    return max_value;
}

Attention

分解成两部分枚举组合后，合并时不可简单的笛卡尔积，因为这里笛卡尔积即两层 for 循环，时间复杂度会变为 $O(2^{N/2}\ast 2^{N/2})=O(2^N)$ ，这和直接枚举所有组合的复杂度是一样的，因此合并还是需要一定的技巧。在分治方法中，合并永远是最关键的部分。

3.2 合并复杂度的陷阱

既然分解得越多，二进制枚举的复杂度就越低，那是不是分解越多越好呢？

实际上并非如此。虽然枚举复杂度在降低，但合并复杂度会急剧上升：

分法	枚举复杂度	合并复杂度	总复杂度
2 分	O(2^(n/2))	O(2^(n/2))	O(2^(n/2)) ✔
3 分	O(2^(n/3))	O(2^(2n/3))	**O(2^(2n/3))**❌
4 分	O(2^(n/4))	O(2^(n/2))	**O(2^(n/2))**✔

为什么合并变复杂了？

• 2 分法：一个部分固定，另一个部分用二分查找 → O(2^(n/2))
• 3 分法：两个部分的笛卡尔积，第三个部分二分查找 → O(2^(n/3) × 2^(n/3)) = O(2^(2n/3))
• 4 分法：2+2 笛卡尔积，然后同 2 分法 → O(2^(n/2))

Note

这里二分查找的复杂度是 O(log(2^n)) = O(n) 级别，相比 2^n 可以忽略不计。

这个问题的最优分割方式是二分法，即将物品分成两部分进行枚举和合并 。

三分法最后合并阶段还是得转换成合并 2/3(前两部分的笛卡尔积)+1/3，因此复杂度反而比二分法的 1/2+1/2 高。

4 分法之所以和 2 分法有同的复杂度，是因为它的合并方式还是变成了二分法的合并方式。4 分法的相比 2 分法，会在 1/4 阶段就进行剪枝，但这点优化只有在 n 非常大时才会体现出来。

由此可见，分治的 ” 分 ” 要适度，过度细分会让 ” 治 ” 变得更复杂！

4 附：各方法的运行结果

knapsack01_float_to_int: 1050.07 (Time: 0.96 ms)
knapsack01_float_binary_enum: 1050.07 (Time: 46.73 ms)
knapsack01_float_recursive: 1050.07 (Time: 2.79 ms)
knapsack01_float_half_enum: 1050.07 (Time: 0.10 ms)