-1

Let's say I have two resources X, Y which amount is well known. Next I have n items, where each item is described by it cost: x, y. How to tell how many items I can produce (maximum)? I would appreciate any pseudocode or c/c++ algorithm which helps me to determine that.

abc
  • 2,371
  • 3
  • 25
  • 36
  • 3
    I assume x,y varies for each item? If so - you got yourself a variation of the [knapsack problem](http://en.wikipedia.org/wiki/Knapsack_problem) with an extra dimension. – amit Dec 04 '12 at 19:34
  • Yes, it is. Can you tell me more? I solve knapsack problem once, but only when I have value of an item. Here I don't know what put into 3D matrix? In standard Knapsack I put value of item :S – abc Dec 04 '12 at 19:40

1 Answers1

1

You can solve it with a variation of knapsack with 3D space instead of 2D.

In here, the "profit" of each item is 1, and you try to maximize it. The weights are the pairs (x,y) for each item.

The idea of 3D knapsack is just the same, but with an extra dimension in the recursive step. This thread discusses this issue exactly.

The recursive formula for the DP solution for the problem (assuming integers x,y) is (taken from the cited question's answer):

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

Let's do it with your example:

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
Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • I still got problem. How to act i.e. for input X = 3 Y = 6; x1 = 3, y1 = 3 x2 = 1, y2 = 4 x3 = 2, y3 = 2 outer loop by Y inner loop by X for first row i will discover that can be put only in knapsack (3,3) (3,4) (3,5) (3,6) and for next row (2nd) I should know that (3,6) should be replace by item 2nd, because in future item 3rd combined with 2nd would fit that knapsack giving me right answer which is 2. In 2d i just left more valuable item or if they were same lighter. Here becuase x1 < x2 and y1 > y2 i don't know what to do. – abc Dec 04 '12 at 20:05
  • @Kostek:Try doing top-down and you see you get it right. The buttom up is the implementation and it should be equivalent to the top-down approach unless you have some bug. (I started to develop it and I got the 2, but it was messed up I am afraid, I will develop it later [about ~hour-2hours] if you will still be stuck). – amit Dec 04 '12 at 20:22
  • @Kostek: I editted the answer with your example and showed a top-down solution to it, you get 2 (as expected). The buttom-up solution does the same basically - so if you get a different result - you have a bug in the implementation. – amit Dec 04 '12 at 21:29