最大乘积切割算法

Question

我正在查看 https://www.geeksforgeeks.org/maximum-product-cutting-dp-36/#:~:text=Given%20a%20rope%20of%20length,is%20more%20than%202%20meters 上发布的问题。

问题陈述是

Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters.

用动态规划可以相当简单地解决。这是他们的解决方案

// A Dynamic Programming solution for Max Product Problem 
int maxProd(int n) 
{ 
   int val[n+1]; 
   val[0] = val[1] = 0; 
   
   // Build the table val[] in bottom up manner and return 
   // the last entry from the table 
   for (int i = 1; i <= n; i++) 
   { 
      int max_val = 0; 
      for (int j = 1; j <= i/2; j++) 
         max_val = max(max_val, (i-j)*j, j*val[i-j]); 
      val[i] = max_val; 
   } 
   return val[n]; 
}

我的问题是，为什么内循环只转到 i/2 而不是 i - 1 才有效？这似乎是利用了对称性。不过max函数也结束了j * val[i - j]，貌似我们忽略了j = i/2 + 1, ..., i - 1.

Answer 1

对problem source给出的算法的解释：

We can see that there are many subproblems which are solved again and again. Since same subproblems are called again, this problem has Overlapping Subproblems property.... Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array val[] in bottom up manner.

虽然这在技术上确实解释了推理，但解释并没有说明一切。原作者没有很好地解释他们对实际代码的思考过程。因此，任何人能做的最好的事情就是猜测他们在想什么。如果你只看 i<=5 个案例，有人可能会争辩说作者看到了这种对称性并将其切断。他们使用 n=5 案例作为 post.

中的示例这一事实可以证实这一论点。

为了进一步解释，下图显示了循环迭代时 max 函数的输出。黄色表示使用 j <= i/2 而不是 j <= i 将跳过的迭代。 j=0 行表示循环开始前的 val 数组，“-”值表示未初始化的值。

这些结果还将展示他们如何进一步简化程序。结果表明，对于每一个大于 4 的 i，最大值总是在 j=3 行。

If we see some examples of this problems, we can easily observe following pattern. The maximum product can be obtained be repeatedly cutting parts of size 3 while size is greater than 4, keeping the last part as size of 2 or 3 or 4. For example, n = 10, the maximum product is obtained by 3, 3, 4. For n = 11, the maximum product is obtained by 3, 3, 3, 2.

Answer 2

让我们暂时从 DP 解决方案退一步，因为我认为这是从解决方案的数学属性得出的。

假设你必须对一根长度为 n 的绳子进行 k 次切割。这比您所陈述的问题更具限制性，您可以在其中进行任意（正）数量的削减。理想的解决方案是什么样的？如果你被允许进行任何你想要的切割，而不仅仅是整数切割，最好的答案是将绳子切成 k 块，大小为 n/k。为什么是这样？好吧，假设你不这样做。这意味着某些部分必须大于平均值（假设其大小至少为 n/k + ε），而某些部分必须小于平均值（假设其大小最多为 n/k - ε).那么这两块的乘积最多为

(n/k + ε)(n/k - ε)

= (n/k)² - ε².

请注意，此处的 ε 越大 - 也就是说，片段大小的差异越大 - 此产品变得越小。这意味着你最好改变这些碎片的切割方式，使它们的尺寸更接近平均值 n/k。

即使切割必须是整数大小，同样的逻辑也适用。例如，想象一下，两件作品的尺寸至少相差两倍。写下一件的尺寸至少为 m + d，另一件的尺寸最多为 m - d。那么这些件的乘积是m² - d²，所以你最好让它们尽可能接近它们的平均值保持 d 小。

那么为什么上限是n/2？好吧，上面的推理表明，如果我们进行 k 次切割，我们应该使这些值尽可能靠近，特别是对于 k 次切割，任何一块的尺寸都不应该大于⌈n / k⌉。在 k = 2 的情况下，最大的一块永远不会大于⌈k/2⌉。我认为这就是这个界限的来源。

事实上，我相当确定这个论点意味着这个问题有更快的解决方案。与其在每个点上砍掉任意数量并谈论进行任意数量的削减，不如迭代所做的削减数量。对于每个切割次数，我们知道切割的尺寸应该是多少 - 使碎片的尺寸尽可能接近平均值。不需要使用任何 DP 来做到这一点。在伪代码中：

max_cut = 0
for cuts = 2 to n:
    average_rounded_down = n // cuts
    pieces_above_average = n % cuts
    pieces_below_average = cuts - pieces_below_average
    value_of_this_cut = (average_rounded_down) ** pieces_below_average + (average_rounded_down + 1) ** pieces_above_average
    if max_cut < value_of_this_cut:
         max_cut = value_of_this_cut

这在时间 O(n) 中运行，忽略了将值提升到不同幂的成本（公平地说，这不是 O(1)）。

我相当确定这可以通过使用像二进制搜索这样的东西来改进对最佳切割次数的搜索来进一步改进，但是可惜我现在没有时间弄清楚如何去做。 :-)

最大乘积切割算法

Maximum product cutting algorithm

language-agnostic

algorithm

dynamic-programming