带双重重量约束的背包问题求解及大规模场景适配

问题拆解 #

你需要解决的是带双类别重量约束的0-1背包问题，核心要求：

1. 选择同一组物品，满足总重量≤W、第一类物品总重≤W1、第二类物品总重≤W2，最大化总价值；
2. 不仅输出最大价值，还要返回选中的物品集合；
3. 适配15万物品、总重量上限6e6的大规模数据场景（经典DP完全无法支撑）。

一、小规模场景：多约束DP实现（带回溯） #

对于物品数量少、约束上限小的情况，可通过二维DP（优化自三维）实现精确解，同时通过回溯记录选中物品。

1. 状态定义 #

用二维数组dp[w1][w2]表示：第一类物品总重为w1、第二类为w2时的最大价值，同时满足w1 + w2 ≤ W。额外用prev数组记录每个状态的来源，方便回溯。

2. 状态转移逻辑 #

遍历每个物品，按类别处理：

• 若为第一类物品：加入后不违反W1和总重量约束时，比较「加入该物品后的价值」与「原价值」，取大值更新DP表，并记录选择路径；
• 若为第二类物品：同理，判断W2和总重量约束后更新DP表。

3. 代码实现（含回溯） #

def multi_constraint_knapsack(W, W1, W2, items):
    # items格式: [(类型(0/1), 重量, 价值, 物品索引), ...]
    # 初始化DP表，dp[w1][w2] = 当前状态下的最大价值
    dp = [[0] * (W2 + 1) for _ in range(W1 + 1)]
    # prev[w1][w2] = (是否选中当前物品, 前状态w1, 前状态w2, 物品索引)
    prev = [[(False, 0, 0, -1)] * (W2 + 1) for _ in range(W1 + 1)]

    for item in items:
        typ, wt, val, idx = item
        # 逆序遍历，避免重复选择同一物品（0-1背包核心特性）
        for w1 in range(W1, -1, -1):
            for w2 in range(W2, -1, -1):
                current_total = w1 + w2
                if current_total > W:
                    continue
                # 处理第一类物品
                if typ == 0:
                    new_w1 = w1 + wt
                    if new_w1 <= W1 and (new_w1 + w2) <= W:
                        if dp[new_w1][w2] < dp[w1][w2] + val:
                            dp[new_w1][w2] = dp[w1][w2] + val
                            prev[new_w1][w2] = (True, w1, w2, idx)
                # 处理第二类物品
                else:
                    new_w2 = w2 + wt
                    if new_w2 <= W2 and (w1 + new_w2) <= W:
                        if dp[w1][new_w2] < dp[w1][w2] + val:
                            dp[w1][new_w2] = dp[w1][w2] + val
                            prev[w1][new_w2] = (True, w1, w2, idx)

    # 找到最大价值对应的w1和w2组合
    max_val = 0
    best_w1, best_w2 = 0, 0
    for w1 in range(W1 + 1):
        for w2 in range(W2 + 1):
            if w1 + w2 <= W and dp[w1][w2] > max_val:
                max_val = dp[w1][w2]
                best_w1, best_w2 = w1, w2

    # 回溯获取选中物品
    selected = set()
    curr_w1, curr_w2 = best_w1, best_w2
    while curr_w1 != 0 or curr_w2 != 0:
        sel, p_w1, p_w2, idx = prev[curr_w1][curr_w2]
        if sel and idx != -1:
            selected.add(idx)
            curr_w1, curr_w2 = p_w1, p_w2
        else:
            # 当前状态无来源，说明是初始状态，停止回溯
            break

    return max_val, selected

# 测试用例
items = [
    (0, 10, 60, 0),   # 第一类，索引0
    (0, 20, 100, 1),  # 第一类，索引1
    (1, 30, 120, 2)   # 第二类，索引2
]
W = 50
W1 = 30
W2 = 30
max_val, selected = multi_constraint_knapsack(W, W1, W2, items)
print(f"最大价值: {max_val}")
print(f"选中物品索引: {selected}")

二、大规模场景：15万物品的优化方案 #

经典DP时间复杂度为O(n*W1*W2)，对于15万物品+6e6总重量的场景完全不可行，必须采用近似或启发式算法，以下是实用方案：

1. 贪心+局部搜索（首选） #

• 步骤：
  1. 按**价值密度（价值/重量）**对物品排序，优先选择密度高的物品，严格满足三个约束；
  2. 对贪心结果做局部优化：尝试替换1-3个已选物品为未选物品，检查是否能在不违反约束的前提下提升总价值；
• 优势：时间复杂度O(n log n)，实现简单，处理15万物品毫无压力；
• 注意：若物品价值分布极端，可调整排序策略（比如优先选高价值物品，再补充密度高的）。

2. 遗传算法（追求较优解） #

• 核心思路：
  1. 编码：用二进制串表示物品选择（0=不选，1=选）；
  2. 适应度函数：总价值（违反约束则赋予负惩罚值）；
  3. 进化操作：选择适应度高的个体交叉繁殖，随机变异少量基因，迭代多代后取最优个体；
• 优势：能在大规模数据中找到接近最优的解；
• 调参提示：种群大小设为50-200，交叉率0.7-0.9，变异率0.01-0.05，避免过早收敛。

3. 分支定界（需剪枝优化） #

• 思路：
  1. 按价值密度排序物品，计算每个节点的上界（剩余物品按密度最大化选择的价值）；
  2. 若当前节点上界小于已找到的最优解，直接剪枝；
• 适用场景：物品价值较高时剪枝效果好，但对15万物品仍可能较慢，建议先用贪心算出初始最优解，再用分支定界优化。

关键注意事项 #

• 如果总重量W等于W1+W2，只需检查W1和W2的约束，无需额外判断总重量；
• 大规模场景下优先用贪心+局部搜索，实现快、效率高；若必须接近最优解，再考虑遗传算法；
• 物品分类要明确，避免出现跨类物品。

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