It was a warm summer evening...
when my stupid car decided to break down in the middle of the road on my way back from the supermarket. I pushed it to the sideline and decided to walk home. I opened the trunk to take out the grocery and remaining stuff. It was then that I noticed the items were not evenly bagged. Some bags had more heavy items while others had few lighter stuff - some even had a mix of such items. To make it easy for me to carry, I decided to group everything in to two bags and make their weights as close to each other as possible.
Your goal
is to help me rearrange the items in to two shopping bags in such a way that the difference between both bags is close to zero as possible.
Mathematically:
WEIGHT LEFT HAND — WEIGHT RIGHT HAND ≈ 0
Example
If I had only 2 items, Bread and Peanut butter, and the weight of bread is 250 grams and peanut butter is 150 grams, the best way is to carry them separately in two hands.
WLH - WRH = W(BREAD) - W(P.BUTTER)
250 - 150 = 100
The other possibility is :
W(BREAD, P.BUTTER) - W(empty hand) = (250 + 150) - 0 = 400
This is not better than our first case, so you should go with the first one.
Your code should
- take inputs of numbers indicating weights of items in the shopping bag. Units are not important, but they should be the same (ideally kilograms or grams). Input can be done one by one or all at once. You may restrict the total count to 20 items max, if you want.
- The input format/type is up to you to choose, but nothing else should be present other than the weights.
- Any language is allowed, but stick to standard libraries.
- Display output. Again, you're free to choose the format, but explain the format in your post. ie, how can we tell which ones are left hand items and which ones are right hand items.
Points
- Shortest code wins.
Hint
The two possible algorithms that I could think of are differentiation (faster) and permutations/combinations (slower). You may use these or any other algorithm that does the job.