-1

假设我有两个X, Y众所周知的资源。接下来我有 n 个项目，其中每个项目都由它的成本来描述：x, y. 如何判断我可以生产多少件商品（最多）？我将不胜感激任何可以帮助我确定的伪代码或 c/c++ 算法。

4

1 回答 1

1

您可以使用具有 3D 空间而不是 2D 空间的背包变体来解决它。

在这里，每个项目的“利润”为 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 回答