3

可能的重复：
动态规划和背包应用程序

我一直在尝试理解动态编程，但是对于每个新问题，我都会对如何为其编写递归感到有些困惑。

举个问题：有一块L×H的金属板，可以用机器垂直或水平切割成两块。L、H都是整数，切割也沿着整数值发生。有n个矩形图案l（ i) × h(i) , i ≤ n (l , h 也是整数) 其中第 i 个模式的利润为 c(i)。设计一种有效的算法来切割板材，以使总利润最大化。

现在我认为为了解决它，我们将创建一个 LxH 表（将按对角线填充）。但是我们如何形成一个递归来解决这个问题呢？

4

2 回答 2

2

我会为每个 T(L, H) 尝试类似的东西，验证以下之间的最佳选择：

  • 立即收取利润
  • 水平切割所有可能的方式
  • 垂直切割所有可能的方式

就像是：

T(L, H) = max(
    c(L, H),  
    T(i, H)+T(L-i, H), // 0<i<L
    T(L, i)+T(L, H-i)  // 0<i<H
)
于 2012-10-05T21:28:41.830 回答
1

我不明白为什么你真的想在有 dp 关系时使用递归。回溯递归通常效率很低，因为它的复杂度通常为 O(2^N) 或更高。

然而，那些指数算法很像这样：

function rec(state)
    if state = end
       return
    Choose the current element
    rec(state + 1)
    Don't choose the current element
    rec(state + 1)

在你的情况下，这可能是这样的蛮力：

  function rec(rect r)
      if r is empty
        return 0
      Max = 0
      for i = 1 to r.width
          for j = 1 to r.hight
             rect g = cut(r, i, j)
             Max = max(Max, profit(g) + rec(r - g))
      return Max
于 2012-10-05T21:41:27.620 回答