从L个物品选至少M个且总价不超Q的方案数求解优化

问题分析 #

给定L个物品（0 < L < 31），每个物品选或不选，要求选至少M个且总价不超过Q，求符合条件的子集数目。原三维DP解法在L接近31、Q较大时，因状态数过多或递归开销导致超时，而折半搜索是针对这类中等规模（20~40）子集问题的高效解法。

原代码问题点 #

1. 冗余的used数组：递归按pos顺序处理物品，每个物品仅被考虑一次，used数组完全多余，增加了不必要的操作。
2. 三维DP的状态开销：当Q较大时，sumOfItems维度的空间和时间成本显著上升，递归的函数调用开销也会累积。

优化思路：折半搜索 #

将31个物品拆分为两组（比如15个和16个），分别枚举两组的所有子集，再通过组合两组的结果快速统计符合条件的总数：

• 拆分物品：把物品分成A、B两组，每组规模约15~16个，枚举每组所有子集的物品数量和总价。
• 预处理B组：按物品数量分组，每组内的总价排序，方便后续二分查找快速统计符合条件的子集数。
• 组合统计：遍历A组的每个子集，计算B组中需要满足的物品数量和总价条件，用二分查找快速累加符合条件的B组子集数。

实现代码 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    int L, M, Q;
    cin >> L;
    vector<int> P(L);
    for (int i = 0; i < L; ++i) {
        cin >> P[i];
    }
    cin >> M >> Q;

    // 拆分两组
    int mid = L / 2;
    vector<pair<int, int>> left; // (物品数量, 总价)
    vector<pair<int, int>> right;

    // 枚举左半部分所有子集
    for (int mask = 0; mask < (1 << mid); ++mask) {
        int cnt = 0, sum = 0;
        for (int i = 0; i < mid; ++i) {
            if (mask & (1 << i)) {
                cnt++;
                sum += P[i];
            }
        }
        if (sum <= Q) { // 提前过滤总价超标的子集
            left.emplace_back(cnt, sum);
        }
    }

    // 枚举右半部分所有子集
    int right_size = L - mid;
    for (int mask = 0; mask < (1 << right_size); ++mask) {
        int cnt = 0, sum = 0;
        for (int i = 0; i < right_size; ++i) {
            if (mask & (1 << i)) {
                cnt++;
                sum += P[mid + i];
            }
        }
        if (sum <= Q) {
            right.emplace_back(cnt, sum);
        }
    }

    // 预处理右半部分：按物品数量分组，每组内总价排序
    vector<vector<int>> right_groups(right_size + 1);
    for (auto &p : right) {
        right_groups[p.first].push_back(p.second);
    }
    for (auto &vec : right_groups) {
        sort(vec.begin(), vec.end());
    }

    ll ans = 0;
    // 遍历左半部分每个子集，统计符合条件的右半部分子集数
    for (auto &p : left) {
        int cnt1 = p.first;
        int sum1 = p.second;
        if (sum1 > Q) continue;

        // 需要右半部分至少选 need_cnt 个物品
        int need_cnt = max(0, M - cnt1);
        // 右半部分最多选 right_size 个
        for (int cnt2 = need_cnt; cnt2 <= right_size; ++cnt2) {
            int max_sum = Q - sum1;
            if (max_sum < 0) continue;
            // 二分查找right_groups[cnt2]中<=max_sum的元素个数
            auto &vec = right_groups[cnt2];
            ans += upper_bound(vec.begin(), vec.end(), max_sum) - vec.begin();
        }
    }

    cout << ans << endl;
    return 0;
}

代码说明 #

• 子集枚举：用位掩码mask枚举每组的所有子集，计算每个子集的物品数和总价，提前过滤总价超过Q的子集减少后续计算。
• 分组排序：右半部分按物品数量分组并排序，使得可以用upper_bound快速统计符合总价条件的子集数。
• 时间复杂度：枚举两组子集的时间是O(2^{(L/2))，对于L=31，2}15=32768，2^16=65536，总枚举量约10万，远低于三维DP的百万级状态，加上二分查找的O(logN)，整体时间完全符合1秒限制。

内容的提问来源于stack exchange，提问作者Tomás Nascimento