3

我正在努力理解这个问题：

给你一块长方形布，尺寸为 X 乘 Y，其中 X 和 Y 是正整数，以及可以使用该布制作的 n 个产品的列表。对于 [1,n] 中的每个产品 i，您知道需要一个尺寸为 ai×bi 的矩形布，并且该产品的最终售价为 ci。假设 ai、bi 和 ci 都是正整数。您有一台机器可以将任何矩形布片水平或垂直切成两块。设计一种算法，找到切割 X 乘 Y 块布的最佳策略，以便由所得块制成的产品给出最大的销售价格总和。您可以随意制作任意数量的给定产品副本，如果需要，也可以不制作。

尽管我实际上已经正确地实现了动态编程解决方案，但我很难理解/证明为什么一个简单的问题解决方案会在指数时间内运行。我认为这首先表明对指数算法缺乏了解，但我现在主要关心的是上述情况。

我知道动态编程解决方案允许我通过记忆我已经完成的工作来节省工作。动态规划的运行时间应该是 O((W*H)(n+w+h)) 或 O(n^3)/多项式。这是因为我正在尝试每个可能的布片宽度和高度。对于每个可能的布块宽度和高度，我尝试每种可能的垂直、水平和块尺寸切割。（我也有点困惑，为什么 n 在时间复杂度中是必要的，因为如果你尝试每一个可能的水平和垂直切割，也应该尝试每一个可能的部分）。

如果我关闭了记忆，那应该给我蛮力方法，这涉及解决整个树。这应该是多项式或 O(2^n)。为什么？具有 O(2^n) 时间复杂度的算法不应该由二叉树表示吗？看起来这个问题的天真的解决方案不会是二元的。

4

3 回答 3

1

线性优化

  • 可以使用线性规划\优化来解决超过 1 个变量的问题，

  • 时间：O(n)

  • 空间：O(1)

动态规划

  • 解决关于 k 变量的问题可以通过动态规划\优化来完成，

  • 时间：O(Π{ Si } * T(Δ Ij) * c) for i: 1..k，其中 Si 是第 i 个可变域大小，Ij 是第 j 个输入大小，c 是计算次数的“常数”在模型中

  • 空间：O(Π{ Si }) 基本上需要的存储空间是|S| 维矩阵

讨论：

〜基本上你提到的是2变量的情况，解决2变量问题的简单动态规划的最佳版本将具有O（（W * H）（n + w + h））或通常 O(3^n) “输入大小泛化为 n”

~ 我曾经使用维特比动态规划算法编写了一个语言学相似性库，该算法在隐马尔可夫模型上使用概率 N-gram max-min 函数（存储为 3D 矩阵）

~ 如果你有兴趣，它是用 Java 编写的：下载

资料来源：

于 2013-03-24T19:40:45.290 回答
0

为了帮助了解为什么它是 2^n（二叉树），将可能的削减视为是/否决定：我在这里削减吗？还是这里？还是这里？每个是/否二元决策都会产生一个必须检查的可能性子树。

这个问题没有用二叉树表示的原因是因为我们只对叶子感兴趣。具体来说，在最优叶子中。从根到那片叶子的路径是最优切割的解决方案。树本身就是可能的解空间。

于 2014-12-04T03:11:49.307 回答
0

这个问题听起来像是背包问题的衍生问题（即，从给定的空间中获得尽可能多的价值）。考虑到这一点，请看这里。有一节解释了简单的解决方案（并用二叉树表示），并显示了重叠的子问题。

如果你不明白你的问题与背包问题的相同之处，你应该从那里开始。

于 2013-03-24T18:19:07.003 回答