如何解决最大数量限制的棒材切割问题允许削减？ [英] How to solve rod cutting p‌r‌o‌b‌l‌e‌m with limit on maximum no. of cuts allowed?

问题描述

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

I know how rod cutting problem is solved using dynamic programming. But when we have limit on maximum no of cuts that is allowed, dynamic programming fails to give correct answer.Even I couldn't think of a recursive solution for the problem. Help.

这是问题所在，

确定通过切割杆和出售零件可获得的最大收益。

长度为N的一根棒，以及长度为i的一根棒的价格表P（i）。在给定的棒上最多只能进行K条切割。

HERE IS THE PROBLEM,
Determine the maximum revenue obtainable by cutting up the rod and selling the pieces.
Given a rod of length N, and table of prices P(i) for the rod of length i.You can make no more than K cuts on the given rod.

示例：

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 |

example:
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 |

通过将棒切成2片（最大切数= 1小于K = 3），可获得的最大收益为31长度6和4。

maximum obtainable revenue is 31 by cutting the rod into 2 pieces (total no of cuts =1 which is less than K=3) of length 6 and 4.

推荐答案

我们可以通过添加第二维来扩展动态编程解决方案，第二维是到目前为止的切割数量。

We can extend the dynamic programming solution by adding a 2nd dimension which is the number of cuts thus far.

D [n] [k] ，长度 n 使用精确的 k 削减，可以定义如下：

D[n][k], the maximum revenue for a rod of length n using exactly k cuts, can be defined as follows:

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

因为我们最多需要 K 削减而不是精确地削减，最大收益将是：

Since we want at most K cuts, not exactly, the maximum revenue will be:

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

这将是 O（N²K），因为我们需要遍历所有 k （与 O（N²）来解决经典问题）。

This will be O(N²K), since we need to loop over all k (compared to O(N²) for the classic problem).

（ JA va）的代码：

(Java) code for this:

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);

实时演示。

这篇关于如何解决最大数量限制的棒材切割问题允许削减？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！