我正在研究这个问题:
您被给予一个长为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)的算法不应该可以用二叉树表示吗?似乎朴素的解决方案并不是二叉的。
虽然我已经正确实现了动态规划解决方案,但我很难理解/证明为什么朴素的方法会导致指数级运行时间。我认为这首先表明我对指数级算法的理解不足,但现在我主要关心上述情况。
我理解动态规划解决方案可以通过记忆我已经完成的工作来节省工作量。动态规划的运行时间应为O((W * H)(n + w + h))或O(n ^ 3)/ 多项式时间。这是因为我尝试着每个可能的布料碎片的宽度和高度。对于每个可能的布料碎片的宽度和高度,我尝试着每个可能的垂直、水平和大小的切口。 (我有点困惑为什么时间复杂度中需要n因为如果您尝试每个可能的水平和垂直切割,那么应该也尝试了每个可能的布料碎片)。
如果我关闭记忆化,则得到暴力方法,它涉及解决整个树。这应该是多项式或O(2 ^ n)。为什么?时间复杂度为O(2 ^ n)的算法不应该可以用二叉树表示吗?似乎朴素的解决方案并不是二叉的。
O(2^n)
。 - phs