We have two boxes, size of 20 and 30. We want to pack fruits in the boxes in a way that gives us the biggest revenue.
Price Size APPLES 5 19 ORANGES 11 11 BANANAS 2 5 KIWI 8 16 MANGO 22 23 CHERRY 2 9
Example looks very similar to rod cutting problem. First solve rod cutting problem for the first box (size of 20) and then with the remaining items solve rod cutting problem for the second box (size of 30). Or vice versa.
But then I came up with this example: If we first pack first box (size of 20), the best combination leads to Oranges (11|11) and Bananas (2|5) which gives us price 13 and size 16. Rod cutting 'algorithm' will always choose best Price/Size combination.
Now lets continue with the second box (size of 30). We pack Mango (22|23) and that's it. We have ran out of space for any other fruit.
Total revenue of two boxes in this example equals to 13 + 22 = 35. However, we could have had revenue of 37, with Cherry (2|9) in the first box and Bananas (2|5) in the second one.
If we first packed the second, bigger box, we would get correct result. But does that way (packing boxes starting with bigger ones) always works? I believe, despite starting with bigger boxes, there will always be the case where this algorithm will fail. What would be better approach to solve this problem?
EDIT: In this example we have two boxes but it could be N boxes. I am looking for a solution that would solve this problem in general, N boxes.
