algorithm - 动态规划-复杂性

Question

我有一个家庭作业问题，一段时间以来我一直在努力解决，但我终其一生都无法解决。

我有一张尺寸为 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;
}

Answer 1

递归案例是指数级的，因为您可以在开始时选择将纸张切割 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