algorithm - 如何解决最大数量限制的棒材切割 p‌r‌o‌b‌l‌e‌m允许削减？

Question

我知道如何使用动态规划解决切杆问题。但是当我们对允许的最大切割次数有限制时，动态规划无法给出正确的答案。即使我也想不出该问题的递归解决方案。帮助。

问题来了，
求出将棒子切段卖掉能获得的最大 yield 。
给定一根长度为 N 的杆，以及长度为 i 的杆的价格表 P(i)。您可以在给定的杆上进行不超过 K 次切割。

例子:
N=10
K=3
| p(1) = 1 | p(2) = 5 | p(3) = 8 | p(4) = 9 |p(5) = 10| p(6) = 22 | p(7) = 17 | p(8) = 20 | p(9) = 24 | p(10) = 30 |

将杆切割成长度为 6 和 4 的 2 段(总切割次数 =1，小于 K=3)，可获得的最大 yield 为 31。

Answer 1

我们可以通过添加第二个维度来扩展动态规划解决方案，该维度是到目前为止的切割次数。

D[n][k]，长度为 n 的杆使用恰好 k 切割的最大 yield ，可以定义为如下:

D[n][k] = max(price[i] + D[n-i-1][k-1]) for all i in {1, 2, ..., n}

由于我们希望至多 K 削减，而不是恰好，因此最大收入将是:

maxRevenue(N) = max(D[N][k]) for all k in {1, 2, ..., k}

这将是 O(N²K)，因为我们需要遍历所有 k(与经典的 O(N²) 相比)问题)。

---

(Java)代码:

int[] price = {1, 5, 8, 9, 10, 22, 17, 20, 24, 30};
int N = price.length;
int K = 3;
int[][] D = new int[N+1][K+1];

for (int n = 1; n <= N; n++)
    D[n][0] = price[n-1];

for (int k = 1; k <= K; k++)
for (int n = 0; n <= N; n++)
for (int i = 0; i <= n-1; i++)
    D[n][k] = Math.max(D[n][k], price[i] + D[n-i-1][k-1]);

int best = 0;
for (int k = 0; k <= K; k++)
    best = Math.max(best, D[N][k]);

System.out.println(best);

Live demo .