Python物品分装组合求解：用[5,25,30]容量盘子装133件物品

已知总物品数totalOfItems=133，盘子容量为[5,25,30]，需要找出所有能恰好装下133件物品的盘子组合（例如4×25+30+5、4×30+5等）。

你之前的回溯代码未成功，核心问题是误用了对象属性arr[i].numParcelsWillFit（实际应直接操作数值数组），且未对结果做数量统计整理。以下是修正后的实现：

修正后的回溯代码 #

def find_combination(target, capacities):
    combinations = []
    
    def backtrack(remaining, path, start):
        # 找到有效组合，整理成易读格式
        if remaining == 0:
            count = {}
            for cap in path:
                count[cap] = count.get(cap, 0) + 1
            # 按容量从大到小排序输出
            combo_parts = []
            for cap in sorted(count.keys(), reverse=True):
                if count[cap] == 1:
                    combo_parts.append(f"{cap}")
                else:
                    combo_parts.append(f"{count[cap]}×{cap}")
            combinations.append("+".join(combo_parts))
            return
        # 剩余物品为负，终止递归
        if remaining < 0:
            return
        # 从start开始遍历，避免重复组合（如25+30和30+25视为同一组合）
        for i in range(start, len(capacities)):
            cap = capacities[i]
            path.append(cap)
            backtrack(remaining - cap, path, i)  # 允许重复使用同一种盘子
            path.pop()  # 回溯，移除最后添加的盘子
    
    # 先对容量降序排序，让结果格式更统一
    capacities_sorted = sorted(capacities, reverse=True)
    backtrack(target, [], 0)
    return combinations

# 调用示例
total = 133
plates = [5,25,30]
result = find_combination(total, plates)

# 输出结果
print("所有恰好装下的组合：")
for idx, combo in enumerate(result, 1):
    print(f"{idx}. {combo}")

代码说明 #

• backtrack函数通过递归尝试每种盘子，start参数确保组合不重复（避免顺序不同但内容一致的结果）
• 找到有效组合时，统计每种盘子的使用数量，转换成数量×容量的易读格式
• 使用path.pop()替代remove，避免因重复元素导致的错误回溯
• 对容量降序排序，让结果中大容量盘子在前，与示例格式匹配

运行结果 #

执行后会输出所有符合要求的组合，部分结果如下：

1. 4×30+5
2. 3×30+2×25+3×5
3. 2×30+3×25+8×5
4. 4×25+30+5
5. 5×25+8×5
...

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