有限集管材切割优化求解：Dynamic Programming的Python实现求助

问题背景 #

• 切割需求：需产出6根61cm、5根27cm、4根67.97cm的管材
• 厂商原管材规格：12cm、24cm、36cm、48cm、60cm、72cm、84cm、96cm、120cm
• 切割规则：
  • 切割件长度不能超过原管材长度
  • 切割剩余的废料不可拼接复用（例如：从96cm管材切出61cm后剩余35cm，可再切24cm，剩下的11cm为废料，无法将多个短废料拼接使用）

需求：编写Python代码，计算满足切割需求的最小总废料量，同时返回各规格原管材的使用数量。已知可通过动态规划（DP）求解，但实现过程中遇到困难，尝试生成的初步代码存在问题，现有代码如下：

def min_waste(pieces, lengths):
    # 创建3D表存储子问题结果
    dp = [[[0 for _ in range(len(lengths)+1)] for _ in range(len(lengths)+1)] for _ in range(len(pieces)+1)]

    # 用最大值初始化表
    for i in range(len(pieces)+1):
        for j in range(len(lengths)+1):
            for k in range(len(lengths)+1):
                dp[i][j][k] = float('inf')

    # 基础情况：当需要0根某长度管材时，废料为0
    for j in range(len(lengths)+1):
        for k in range(len(lengths)+1):
            dp[0][j][k] = 0

    # 求解子问题
    for i in range(1, len(pieces)+1):
        for j in range(1, len(lengths)+1):
            for k in range(len(lengths)+1):
                if pieces[i-1] <= lengths[j-1]:
                    # 如果当前零件能放入当前长度的原管材，尝试放入并比较废料量
                    dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k] + lengths[j-1] - pieces[i-1])

                if k > 0:
                    # 如果当前零件无法放入当前长度，尝试用更长的管材
                    dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k-1])

    # 最小废料量为表的右下角值
    return dp[-1][-1][-1]

# 测试函数
pieces = [61, 27, 67.93]
lengths = [12, 24, 36, 48, 60, 72, 84, 96, 120]
print(min_waste(pieces, lengths))

现有代码的问题 #

1. 状态定义错误：3D DP数组的维度未对应实际需求（未考虑每种管材的需求数量，仅单存长度），无法覆盖多数量的切割需求
2. 状态转移逻辑错误：未考虑同一根原管材可切割多个小零件的场景，也未统计各规格原管材的使用次数
3. 输入参数缺失：pieces仅传入了需要的管材长度，未包含对应的需求数量，无法准确计算满足所有需求的废料量

改进的动态规划实现 #

针对一维下料问题，设计DP状态为dp[a][b][c]，代表完成a根61cm、b根27cm、c根67.97cm的切割需求时，产生的最小废料量，同时记录对应的原管材使用计数。

from collections import defaultdict

def pipe_cutting_optimization():
    # 切割需求：(长度, 数量)
    demands = [(61, 6), (27, 5), (67.97, 4)]
    # 厂商提供的原管材规格，按降序排列便于优先尝试大尺寸
    stock_lengths = sorted([12, 24, 36, 48, 60, 72, 84, 96, 120], reverse=True)
    max_a, max_b, max_c = demands[0][1], demands[1][1], demands[2][1]

    # 初始化DP表：dp[a][b][c] = (最小废料量, 原管材使用计数)
    INF = float('inf')
    dp = [[[(INF, defaultdict(int)) for _ in range(max_c+1)] for __ in range(max_b+1)] for ___ in range(max_a+1)]
    # 基础情况：0需求时废料0，无管材使用
    dp[0][0][0] = (0, defaultdict(int))

    for a in range(max_a + 1):
        for b in range(max_b + 1):
            for c in range(max_c + 1):
                current_waste, current_counts = dp[a][b][c]
                if current_waste == INF:
                    continue
                # 尝试使用每种规格的原管材
                for stock in stock_lengths:
                    remaining = stock
                    new_a, new_b, new_c = a, b, c
                    # 尝试切割67.97cm的管材
                    while new_c < max_c and demands[2][0] <= remaining:
                        new_c += 1
                        remaining -= demands[2][0]
                    # 尝试切割61cm的管材
                    while new_a < max_a and demands[0][0] <= remaining:
                        new_a += 1
                        remaining -= demands[0][0]
                    # 尝试切割27cm的管材
                    while new_b < max_b and demands[1][0] <= remaining:
                        new_b += 1
                        remaining -= demands[1][0]
                    # 计算新的废料量和计数
                    new_waste = current_waste + remaining
                    new_counts = current_counts.copy()
                    new_counts[stock] += 1
                    # 更新DP状态
                    if new_waste < dp[new_a][new_b][new_c][0]:
                        dp[new_a][new_b][new_c] = (new_waste, new_counts)

    # 获取最终结果
    total_waste, stock_usage = dp[max_a][max_b][max_c]
    # 格式化输出
    print(f"最小总废料量: {round(total_waste, 2)} cm")
    print("原管材使用数量:")
    for length in sorted(stock_usage.keys()):
        print(f"- {length}cm: {stock_usage[length]} 根")
    return total_waste, stock_usage

# 执行优化
pipe_cutting_optimization()

代码说明 #

• 按降序遍历原管材规格，优先尝试大尺寸管材以减少总使用量
• 针对每个状态，尝试用当前原管材切割尽可能多的需求零件，更新后续状态的废料量和计数
• 使用三维DP数组记录每个需求完成度下的最优解，确保覆盖所有可能的切割组合

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