小约束下基于位掩码的装箱问题求解代码超时优化咨询

原代码超时原因分析 #

原代码的时间复杂度为O(n * 3^n)：

• i遍历最多n个箱子数（n≤20）
• 每个i下遍历所有2^n个状态
• 每个状态枚举所有子掩码，所有状态的子掩码总数量为3^n，n=20时3^20≈3.5e9

相乘后总运算量达到7e10级别，远超常规程序1s内可处理的1e8运算上限，因此触发时间超限。

核心优化方向 #

1. 优化DP状态设计，将复杂度降至O(n * 2^n) #

我们重构状态定义，避免重复枚举子掩码：
定义dp[mask]为一个二元组(min_cnt, max_remain)，其中：

• min_cnt：装下mask对应物品所需的最少容器数量
• max_remain：在使用最少容器的前提下，最后一个容器的最大剩余承重

转移逻辑：对每个状态mask，尝试将未装入的第k个物品加入，有两种选择：

• 如果当前最后一个容器的剩余空间≥arr[k]，直接放入，容器数不变，剩余空间减少arr[k]
• 否则新开一个容器放arr[k]，容器数+1，剩余空间为w - arr[k]

两种情况选择更优的结果：容器数更少优先，容器数相同时剩余空间更大优先。

2. 预处理优化 #

• 先过滤重量为0的物品，这类物品不占用容器空间，可直接减少n的规模
• 将物品按重量从大到小排序，能更快得到更优状态，减少无效更新
• 重量和数组sums的计算可优化为O(2^n)复杂度，通过lowbit运算实现：

for (int i = 1; i < (1 << n); i++) {
    int lowbit = i & -i;
    int pos = __builtin_ctz(lowbit);
    sums[i] = sums[i ^ lowbit] + arr[pos];
}

优化后代码示例 #

int get_minimum_parcels(int n, int w, vector<int> arr) {
    // 预处理：过滤重量为0的物品，降序排序
    vector<int> tmp;
    for (int x : arr) if (x > 0) tmp.push_back(x);
    sort(tmp.rbegin(), tmp.rend());
    arr = tmp;
    n = arr.size();
    if (n == 0) return 0;

    const int INF = 1e9;
    vector<pair<int, int>> dp(1 << n, {INF, 0}); // (最少箱子数, 最后一个箱子最大剩余)
    dp[0] = {0, 0};

    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask].first == INF) continue;
        for (int k = 0; k < n; k++) {
            if (mask & (1 << k)) continue;
            int new_mask = mask | (1 << k);
            int cnt = dp[mask].first;
            int rem = dp[mask].second;
            int new_cnt, new_rem;

            if (rem >= arr[k]) {
                // 直接放最后一个箱子
                new_cnt = cnt;
                new_rem = rem - arr[k];
            } else {
                // 新开一个箱子
                new_cnt = cnt + 1;
                new_rem = w - arr[k];
            }

            // 更新新状态，优先更少箱子，相同箱子优先更大剩余
            if (new_cnt < dp[new_mask].first || (new_cnt == dp[new_mask].first && new_rem > dp[new_mask].second)) {
                dp[new_mask] = {new_cnt, new_rem};
            }
        }
    }

    return dp[(1 << n) - 1].first;
}

可选剪枝优化 #

如果需要进一步压缩运行时间，可以增加以下剪枝：

• 提前计算所有物品总重量除以w向上取整的值作为下界，一旦DP过程中达到该下界可直接返回
• 相同重量的物品可以合并处理，减少重复状态枚举

内容的提问来源于stack exchange，提问作者code_it