3

重複の可能性:
動的プログラミングとナップザック アプリケーション

私は動的プログラミングを理解しようとしてきましたが、新しい問題が発生するたびに、再帰の書き方について少し混乱しています。

次の問題を考えてみましょう: L × H の金属シートがあり、機械で垂直または水平に 2 つに切断できます。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-relation を使用しているときに、なぜ再帰を本当に使用したいのかわかりません。バックトラッキング再帰は、その複雑さが通常 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 に答える