动态规划矩阵计算问题

Question

销售鱼竿业务，每根鱼竿的价格取决于其长度。给定价格表

T

，其中

T[i]

是长度为

i

的棒的价格（美元），任务是将长度为

l

的棒切成碎片，以使总售价最大化。

给定杆长度 1 至 6 的

T = [1, 6, 11, 15, 19, 21]

和

l = 12

，目标是确定最佳切割策略以实现利润最大化。

动态方法是定义

PM

（最高价格）和

NB

（切割次数）矩阵，其中

PM[i][j]

使用长度为

j

的片段计算长度为

i

的杆的最高价格，并且

NB[i][j]

记录使用长度为

i

的件数。

初始化：

for all 1 ≤ i ≤ n, PM[i][0] = NB[i][0] = 0.

递归方案：

对于每个整数

1 ≤ i ≤ n

和

1 ≤ j ≤ l

：

这里，

NB[i][j]

是提供上式中最大值的索引

k

。

PM[n][l]

代表可达到的最高总价，

NB[n][l]

计算达到该价格所需的

n

尺寸的件数。

我在递归步骤中遇到问题。对于

[6,12]

矩阵中的条目

[6x12]

，我正在考虑集合 {0,1,2} 中的

k

值，因为

k

以

12/6

为界。我的解释是从这些

k

值中选择最大值。然而，这种方法感觉可能不必要地限制了我的选择

k

。

以下是我对

PM

公式的组成部分的理解：

• [i-j]

  指向正上方的条目。

• [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)

Answer 1

O(1) 非 DP 方法：所有长度均为（总长度）/（num 件），除了（总长度）%（num 件），多了 1。这种简单的方法是可行的，因为长度增加 1 的好处是不会增加长度的。

1 -> 2: +5 value
2 -> 3: +5 value
3 -> 4: +4 value
4 -> 5: +4 value
5 -> 6: +2 value

这表明最佳解决方案是让所有长度尽可能接近平均值。

给定 12 根长度为 1-6 的杆，杆的长度必须为 12-72，否则无解。

所有棋子都应该是地板（长度/12）或天花板（长度/12），其中取天花板的数量为长度％12。

示例

假设长度 = 50。由于 50/12=4 且 50%12 = 2，因此我们有 10 块长度为 4 的块和 2 块长度为 5 的块。该值为 1011 + 215 = 140。

我们可以做得更好吗？由于切割次数是固定的，我们可以做的唯一改变就是移动长度单位。

modification   result (effect on value)
4->3 & 4->5       15->11 & 15->19; net 30->30; no effect
4->3 & 5->6       15->11 & 19->21; net 34->32; bad outcome
4->2 & 4->6       15-> 6 & 15->21; net 30->27; bad outcome
4->2, 4->5, 4->5  15->6, 15->19, 15->19; net 45->44; bad outcome
etc...