-1

X, Yよく知られている 2 つのリソースがあるとします。次に n 個のアイテムがあり、各アイテムは it cost: で表されますx, y。生産できるアイテムの数 (最大) を確認するにはどうすればよいですか? それを判断するのに役立つ疑似コードまたは c/c++ アルゴリズムをいただければ幸いです。

4

1 に答える 1

1

2D ではなく 3D 空間を持つナップザックのバリエーションで解決できます。

ここでは、各項目の「利益」を 1 として、それを最大化しようとします。重みは、各アイテムのペア (x,y) です。

3D ナップザックの考え方はまったく同じですが、再帰ステップに追加の次元があります。このスレッドでは、この問題について正確に議論しています。

問題のDPソリューションの再帰式（整数x、yを想定）は次のとおりです（引用された質問の回答から取得）：

f(item,cost1,cost2) = max {
               f(item-1,cost1,cost2), 
               f(item,cost1-firstCost[i],cost2-secondCost[i]) + profit[i]
                          }

あなたの例でそれをしましょう：

X = 3 Y = 6; item1 = (3,3), item2 = (1,3), item3 = (2,2).

f(3,3,6) = max { f(2,3,6) , f(2,1,4) + 1} 
         = max { max { f(1,3,6), f(1,2,3) + 1 } , max { f(1,1,4) , f(1,-1,2) + 1 } + 1 }
         = max { max { max { f(0,3,6) , f(0,0,3) + 1} , max { f(0,2,3), f(0,-1,0) + 1} +1 },
                 max { max { f(0,1,4), f(0,-2,1) + 1 } , -infinity } +1 } 
         = max { max { max { 0, 1}, max { 0,-infinity} + 1 }, 
                 max { max { 0, -infinity } , -infinity } + 1 }
         = max { max { 1,0 } + 1 }, max { 0, -infinity } + 1 }
         = max { 2,1} = 2
于 2012-12-04T19:41:53.687 に答える