为什么动态规划问题的朴素解法需要指数级时间？

Question

我正在研究这个问题： 您被给予一个长为X，宽为Y的矩形布料，其中X和Y是正整数，并且还有一个可以使用该布料制作的产品列表。对于每个产品i（i = 1至n），您都知道需要一个长为ai，宽为bi的布料矩形，而该产品的最终销售价格是ci。假设ai，bi和ci都是正整数。您拥有一台机器，可以将任何长方形布料切成两片，水平或垂直地，设计一种算法，以便切割出的布料碎片制成的产品提供最大的销售收入总和。您可以复制某个产品，也可以不复制。

虽然我已经正确实现了动态规划解决方案，但我很难理解/证明为什么朴素的方法会导致指数级运行时间。我认为这首先表明我对指数级算法的理解不足，但现在我主要关心上述情况。

我理解动态规划解决方案可以通过记忆我已经完成的工作来节省工作量。动态规划的运行时间应为O（（W * H）（n + w + h））或O（n ^ 3）/ 多项式时间。这是因为我尝试着每个可能的布料碎片的宽度和高度。对于每个可能的布料碎片的宽度和高度，我尝试着每个可能的垂直、水平和大小的切口。 （我有点困惑为什么时间复杂度中需要n因为如果您尝试每个可能的水平和垂直切割，那么应该也尝试了每个可能的布料碎片）。

如果我关闭记忆化，则得到暴力方法，它涉及解决整个树。这应该是多项式或O（2 ^ n）。为什么？时间复杂度为O（2 ^ n）的算法不应该可以用二叉树表示吗？似乎朴素的解决方案并不是二叉的。

- Mike

---

你不想尝试每一个可能的切割，因为X和Y与n是独立的，并且实际上可能比n指数级更大。你只限制于那些实际上产生一块布料所需的切割，以满足n个产品的需要。 - chepner

此外，多项式时间绝对不等同于 O(2^n)。 - phs

Answer 1

线性优化

• 使用线性规划/优化可以解决一个变量的问题，

• 时间复杂度：O(n)

• 空间复杂度：O(1)

动态规划

• 使用动态规划/优化可以解决k个变量的问题，

• 时间复杂度：对于i: 1..k，其中Si是第i个变量的域大小，Ij是第j个输入的大小，c是模型中计算数量的“常数”，时间复杂度为O(Π{ Si } * T(Δ Ij) * c)

• 空间复杂度：基本上需要存储|S|维矩阵，因此空间复杂度为O(Π{ Si })

讨论：

~ 基本上您提到的是2个变量的情况，简单动态规划的最佳版本解决2个变量的问题的计算时间复杂度为O((W*H)(n+w+h))或一般情况下为O(3^n)，“输入尺寸广义化为n”。

我曾经使用维特比动态规划算法和基于概率的N-gram最大值-最小值函数，利用隐藏马尔可夫模型（存储为3D矩阵）编写过一个语言学相似性库。

如果您感兴趣，它是用Java编写的：下载链接

来源：

• 通过示例学习动态规划

- Khaled.K

Answer 2

这个问题听起来像是背包问题的一个变种（即，在给定的空间内尽可能获得最大价值）。考虑到这一点，请看看这里。有一个部分解释了朴素解法（并用二叉树表示），并展示了重叠子问题。

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

- Nick Mitchinson

Answer 3

为了更好地理解为什么是2^n（二叉树），可以将可能的切割看作是一个个yes/no的决策：我要在这里分割吗？还是这里？或者这里？每一个yes/no的二元决策都会产生一个子集，必须加以考虑。

之所以这个问题不被表示为二叉树，是因为我们只关心叶子节点。具体而言，我们只关心最佳叶子节点。从根节点到该叶子节点的路径就是最佳切割方案。树本身就是可能的解空间。

- Andras