动态规划矩阵计算疑问：杆切割最优定价问题求解

这是杆切割销售业务问题：每根杆的售价由其长度决定。给定价格表T，其中T[i]代表长度为i的杆的售价（单位：美元），我们的任务是将长度为l的杆切割成若干段，最大化总售价。

已知对应长度1至6的价格表T = [1, 6, 11, 15, 19, 21]，杆的总长度l = 12，目标是找出最优切割策略。

动态规划方案 #

定义两个矩阵PM（最大价格）和NB（切割段数）：

• PM[i][j]：使用长度不超过i的段，切割长度为j的杆能获得的最大价格
• NB[i][j]：记录达到上述最大价格时，使用长度为i的段的数量

初始化规则 #

对所有1 ≤ i ≤ n，有PM[i][0] = NB[i][0] = 0。

递归公式 #

对所有整数1 ≤ i ≤ n和1 ≤ j ≤ l，PM[i][j] = max{PM[i-1][j - k*i] + k*T[i]}，其中k为非负整数且满足k*i ≤ j；NB[i][j]取最大值对应的k值。

最终PM[n][l]就是最大总售价，NB[n][l]对应使用长度为n的段的数量。

遇到的问题 #

在6×12矩阵的[6,12]位置，我选取k的集合为{0,1,2}（受限于12/6），但怀疑是否没必要限制k的范围。我对公式各部分的理解如下：

• PM[i-1][j - k*i]指向当前位置正上方的条目
• j - k*i在当前行向左偏移，偏移量随k增大而增加
• k*T[i]计算k段长度为i的杆的总售价

希望明确递归公式及k的正确使用方式。

代码示例 #

T = [0, 1, 6, 11, 15, 19, 21] 
l = 12  
PM = [[0 for _ in range(l + 1)] for _ in range(len(T))]
NB = [[0 for _ in range(l + 1)] for _ in range(len(T))]

for i in range(1, len(T)):
    for j in range(1, l + 1):
        max_profit = 0
        max_k = 0
        for k in range(j // i + 1):
            profit = PM[i - 1][j - k * i] + k * T[i]
            if profit > max_profit:
                max_profit = profit
                max_k = k
        PM[i][j] = max_profit
        NB[i][j] = max_k

for row in PM:
    print(row)
for row in NB:
    print(row)

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