Python如何获取带重量限制的数据集所有合法bin组合方案

现有一组对应不同物品重量的数值列表，定义如下：

weights = [50, 40, 30, 100, 150, 12, 150, 10, 5, 4]

需求是将列表内所有重量值拆分到两个bin中，约束条件为每个bin的重量总和不得超过300。
一个典型的合法拆分方案示例：

bin1 = [150, 150] # 总重300
bin2 = [50, 40, 30, 100, 12, 10, 5, 4] # 总重251

需要枚举所有满足上述重量约束的重量分配组合，以下是具体实现方法。

核心逻辑非常直接，两个bin装完所有物品，本质就是找所有符合要求的物品子集：

• 第一步先做前置校验：计算所有物品总重量，如果总重超过600（两个bin的总容量300*2），直接判定不存在合法方案，不用往下计算。当前给出的重量列表总重为551，小于600，存在合法解。
• 合法拆分的判定标准很简单：选出来放bin1的物品总重≤300，剩下放bin2的物品总重也≤300，这组分配就符合要求。
• 枚举的时候可以做两层优化减少无效计算：
  • 因为bin1和bin2交换本质是同一种分配（如果两个bin没有编号区分的话），只需要枚举长度不超过物品总数一半的子集就行，避免重复统计对称方案。
  • 枚举过程中如果当前凑出来的子集重量已经超过300，直接跳过后续分支，不用继续往下加物品。

from itertools import combinations

weights = [50, 40, 30, 100, 150, 12, 150, 10, 5, 4]
bin_cap = 300
total_weight = sum(weights)
valid_plans = []

# 总重超过两个bin的总容量，直接返回无结果
if total_weight > 2 * bin_cap:
    print("没有符合要求的拆分方案")
else:
    item_count = len(weights)
    # 枚举bin1的所有可能子集，长度最多到总数量一半，避免对称重复
    for bin1_size in range(1, item_count // 2 + 1):
        for bin1_items in combinations(enumerate(weights), bin1_size):
            bin1_weight = sum(w for idx, w in bin1_items)
            # 剪枝：bin1已经超重直接跳过
            if bin1_weight > bin_cap:
                continue
            bin2_weight = total_weight - bin1_weight
            # bin2也不超重，就是合法方案
            if bin2_weight <= bin_cap:
                bin1 = [w for idx, w in bin1_items]
                bin1_indices = {idx for idx, w in bin1_items}
                bin2 = [weights[i] for i in range(item_count) if i not in bin1_indices]
                valid_plans.append((bin1, bin2))

    print(f"共枚举到{len(valid_plans)}种不重复的合法拆分方案，前5种示例：")
    for plan in valid_plans[:5]:
        b1, b2 = plan
        print(f"bin1: {b1}，总重{sum(b1)}；bin2: {b2}，总重{sum(b2)}")

• 如果两个bin有明确区分（比如两个不同编号的箱子，交换bin1/bin2算不同方案），把代码里限制子集长度到item_count//2的逻辑去掉，枚举子集长度从1到item_count-1即可。
• 如果物品数量超过20个，用itertools组合枚举的速度会明显变慢，可以换成0-1动态规划的思路，先记录所有能凑出的不超过300的重量值，再反向回溯对应的物品组合，计算效率会高很多。
• 如果存在多个重量相同的不同物品，不要直接按重量值去重，要保留物品的索引做唯一标识，避免漏掉合法方案。

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