时间戳

首页 > 解决方案 > 如何使用 2D 表最大化棒材切割的产品？

algorithm - 如何使用 2D 表最大化棒材切割的产品？

问题描述

我们得到一根长度为 n 英寸的棒。您可以将其切割成整数长度的不同部分。您的目标是尽可能获得所有零件长度的最大乘积。你必须至少剪一次。假设绳子的长度超过 2 米。参考：https ://www.geeksforgeeks.org/maximum-product-cutting-dp-36/

其他参考：切杆最大化利润的算法

我想使用二维表使用自下而上的动态编程来做这个问题。

假设我们的长度为 5。

                       Length of rod
                [1]   [2]   [3]   [4]   [5]
          [0]    0     0     0     0     0  
Number of [1]    0     1     2     4     6
cuts      [2]    0     1     2
          [3]    0

每个单元格表示我们在给定长度的杆和指定的切割次数下可以获得的最大产品，以及切割后剩余的最大长度。

例如，假设我们需要用切割数 2 和杆长度等于 4 填充单元格。我假设每个单元格除了存储给定长度的最大乘积外，还将存储切割后剩余的最大长度。

在切割长度为 4 后，我们得到最大乘积 4，因为我们将左侧部分切割为 2，右侧部分切割为 2。我们存储两个数字：最大乘积为 4，最大乘积为 2。当我们在单元格 (2, 4) 时，我们可以进行切割，也可以不切割。如果我们不进行切割，那么我们查看当前行。我们循环遍历每个长度。在这种情况下，我们循环长度为 2 和长度为 3。如果长度为 2，则剩余的 4-2=2 并乘以得到 4。然后我们对 3 执行相同操作以获得剩余长度为为 1 并将其乘以 2 得到 2。

另一种选择是进行剪切，然后我们需要查看上排。我们再次从该行的开头循环。然后我们选择最大值。

我的问题是我必须每次循环遍历所有列，即从左到当前单元格，这将使时间复杂度为 O(n^3)。

有没有办法在 O(n^2) 中做到这一点，而不是使用 2D 表？

标签： algorithmdynamic-programmingbottom-up

解决方案

你的逻辑是正确的，结果很明显。您正在尝试解决整个问题，最大杆长度为N，因此您有O(N^2)表条目。j要在一段长度中制作切割编号M，您必须检查从将杆减半到长度为 2 的所有切割；这个列表是O(M)。这些函数的组合为您提供O(N^3)。

但是，完成此操作后，您就有了一个表格，可以让您在O(1)时间内返回您空间中的任何解决方案，因为它是一个直接的表格查找。

考虑到基于 3 的结果，在没有表格的情况下执行此操作是微不足道的。对于 length N，您制作一个floor[N/3]3 的列表，将最后一个N mod 3元素增加到 4。这是一个非常快的O(N)结果。

推荐阅读