1

我有一个家庭作业问题，我一直在尝试解决一段时间，但我一生都无法解决。

我有一张 X*Y 尺寸的表，以及一组较小尺寸的图案，以及与之相关的价格值。我可以水平或垂直切割板材，我必须找到优化的切割模式才能从板材中获得最大的利润。

据我所知，应该有 (X*Y)(X+Y+#ofPatterns) 递归操作。复杂性应该是指数级的。有人可以解释为什么吗？

我想出的伪代码如下：

Optimize( w, h ) {
best_price = 0
    for(Pattern p :  all patterns) {
        if ( p fits into this piece of cloth && p’s price > best price) {best_price = p’s price}
    }
    for (i = 1…n){
       L= Optimize( i, h );
       R= Optimize( w-i, h);
       if (L_price + R_price > best_price) { update best_price}
    }
    for (i = 1…n){
        T= Optimize( w, i );
        B= Optimize( w, h-i);
        if (T_price + B_price > best_price) { update best_price}
    }
return best_price;
}
4

2 回答 2

0

在计算动态规划算法的复杂度时，我们可以将其分解为两个子问题：一个是计算子状态的数量；另一个是计算解决特定子问题的时间复杂度。

但确实，当您不使用记忆化方法时，本质上具有多项式时间复杂度的算法会增加到指数时间复杂度，因为您没有重复使用之前计算的信息。（我很确定您从动态编程课程中了解这部分内容）

无论您是使用记忆法还是自底向上法解决动态规划问题，时间复杂度都保持不变。我认为您遇到的麻烦是您试图在脑海中绘制函数调用图。相反，让我们尝试以这种方式估计函数调用的数量。

你是说有 (X*Y)(X+Y+#ofPatterns) 递归调用。

嗯，是的，也不是。

确实，当您使用记忆化方法时，递归调用的数量只有这么多。因为如果你调用并计算了某个Optimize(w0,h0)，这个值会被存储起来，下次另一个函数Optimize(w1,h1)调用Optimize(w0,h0)时，就不会再做这些多余的工作了. 这就是时间复杂度多项式的原因。

但是在您当前的实现中，一个子问题 Optimize(w0,h0) 获得了许多冗余函数调用，这意味着您的算法中递归调用的数量根本不是多项式的（举个简单的例子，尝试绘制递归的调用图斐波那契数算法）。

于 2013-03-27T23:25:37.810 回答
0

递归情况是指数的，因为您可以在一开始选择将纸张切割为 0 到最大宽度英寸或 0 到最大高度英寸，然后可以选择切割剩余的部分（递归）。

这个问题听起来像是这个棒切割问题的一个更有趣的例子，因为它涉及到两个维度。

http://www.radford.edu/~nokie/classes/360/dp-rod-cutting.html

是一个很好的指南。阅读应该会让你走上正确的轨道，而不会公然回答你的作业。

递归时为什么它是指数的相关部分：

This recursive algorithm uses the formula above and is slow
Code
    -- price array p, length n
    Cut-Rod(p, n)
        if n = 0 then
            return 0
        end if
        q := MinInt
        for i in 1 .. n loop
            q = max(q, p(i) + Cut-Rod(p, n-i)
        end loop
        return q

Recursion tree (shows subproblems): 4/[3,2,1,0]//[2,1,0],[1,0],0//[1,0],0,0//0
Performance: Let T(n) = number of calls to Cut-Rod(x, n), for any x
T(0)=0
T(n)=1+∑i=1nT(n−i)=1+∑j=0n−1T(j)
Solution: T(n)=2n
于 2013-03-27T00:24:07.670 回答