0

This is my first post in this stack, but I have posted on StackOverflow before. Let me declare that I am a coder in search of an algorithm. This is not homework.

Bart has two bags of kiddies wooden blocks, bag A and bag B. All the blocks in both bags are random (and potentially different) heights.
Miss Hoover asks Bart to build a tower from bag A's blocks, and a tower from bag B's blocks, such that both towers are exactly the same height. Bart is allowed to measure the height of each block before building.

All heights are integer values (ref: User24142).

Let's assume I cannot rotate the blocks to use their width, "height" is just used to illustrate a single dimension, an analogous property of the actual object in question.

To solve this for Bart, my first guess would be to combine all blocks in bag A and work out all possible total tower heights, repeat the process for bag B, and then try to find two values in both result sets that match. This is computationally expensive and becomes untenable with large numbers of blocks.

Is this a known problem with a known solution, or do I have no alternative but to grind out the solution from all possible data?

Steve Hibbert
  • 103
  • this begs for dynamic programming (I believe). How many blocks in each bag? are you sure that a combination of blocks in $A$ could potentially match a height in $B$? – Chinny84 Aug 04 '15 at 08:43
  • It seems to relate to the knapsack problem, which is known to be NP complete. https://en.wikipedia.org/wiki/Knapsack_problem I wouldn't calculate all possible heights for both sets though. I would iterate through all possible heights for bag A, and for each height, I would try to match it with a tower from B, remembering all the B-height values I get, including overflows, and then using this information in later iterations. If I knew all the heights were integers or something, I might use a different approach, but this should work. – user24142 Aug 04 '15 at 08:43
  • @Chinny84 Blocks in each bag is unknown, 1 to any value, in either bag. There does not have to be a solution, but you have to try to find a solution to know that there is no case where two towers can match in height. On no solution, more blocks might be added or removed, and when they are, we iterate and try again. – Steve Hibbert Aug 04 '15 at 08:51
  • @user24142 It does look like the knapsack problem, but doubled up. All heights are integers, if that helps. At least with the knapsack problem to go I have a way to look into the problem, so thanks very much for that pointer! – Steve Hibbert Aug 04 '15 at 08:57
  • @Chinny84 For the dynamic programming aspect, I was thinking that factorising the integer block size would allow me to categorise block heights into 'multiples of 2', 'multiples of 3' etc, so that I could work from the large scale blocks first, and then look for suitable candidates to plug the small gaps. Incidentally, if two possible solutions exist, the tallest solution is preferred. – Steve Hibbert Aug 04 '15 at 09:13

1 Answers1

1

This is exactly the subset sum problem, which is NP-complete. Bag A corresponds to the positive numbers, bag B corresponds to the negative numbers.

simonzack
  • 1,701
  • 13
  • 28