Real-life Packing Problem
I came across a problem that I want to solve. I assumed that maths would have an algorithm for this but it turns out that it might not be as straight-forward as I thought.
This is a genuine issue that I’d like help with (and discussed on the latest Wrong, but Useful) so please do help out.
I play a collectable card game called Magic: The Gathering. There are a variety of ways to play: some involving building a deck and taking it with you to a tournament, another involves going along, being given a selection of cards and building your deck with those. I’m organising an event where the cards are provided as you turn up but this is a slightly unusual version called a chaos draft. Essentially, 8 people will arrive and they’ll get three packs of cards each. The ‘chaos’ part is that all these packs are different and have different values. I’d like the players to have a roughly equal total values of packs and therein lies the problem.
There are 24 objects of varying values.
They are to be split into 8 groups of 3.
How can this be done so that the total value of each group has the least variation possible?
What I think so far
Some people on Twitter have pointed me towards bin-packing problems. These are on the right lines but don’t seem to quite do it as they’re concerned with packing a number of objects into the fewest number of bins possible.
Colin Wright said: “This seems to be a small example of a more general problem known to be NP-Complete. In light of that, why do you ask?” (This is what prompted this to become a blog post.) Brief, simplified description of what NP-Complete means.
Colin Beveridge mentioned the ideas along the lines of equal/fair sharing of cakes. That’s probably worth investigating further too.
It’s at times like these that I wish my computer programming skills were better (ie they actually existed) as I’m sure there’s ways to make progress. 24 items isn’t a huge number so it’s plausible to do this by brute force.
My best so far
Having placed the 24 items into 8 groups of three packs, I’ve calculated the standard deviation of those 8 values to be 1.84. My method wasn’t random but is not very systematic either. Can you do better?
If you fancy a go, here are the 24 values:
Thanks for looking. Thanks for any help you can give and, if there are any questions, please ask!