Skip to content

Real-life Packing Problem

June 1, 2016

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.

Background

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.

More mathematically

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:

£2.00
£2.29
£2.50
£2.50
£3.00
£3.00
£3.00
£3.00
£3.23
£3.23
£3.54
£4.17
£4.78
£4.78
£5.20
£5.52
£5.70
£6.00
£6.00
£6.00
£6.18
£7.50
£13.00
£14.06

Thanks for looking. Thanks for any help you can give and, if there are any questions, please ask!

Advertisements

From → Maths

One Comment
  1. How about this (untested):
    Divide the cards’ total by 3 to work out a target total for each set.
    Sort the cards in order of value, starting with the largest.
    Set running totals for set A, B & C to 0
    >>>
    Allocate the largest possible value card to set A, without its total exceeding the target total. Add this value to a running total for set A. (Skip set A if all cards would exceed the target.)
    Do the same for set B, and then set C.
    Return to the arrows >>> above and repeat until all of the cards are allocated.

    If all three sets are skipped, with some cards still left over, you could look at the gap for each set between the running total and the target total, and give the largest remaining card to the biggest gap. Repeat until all the cards are gone.

    This is how I might program a computer to deal with the problem. Not necessarily the most efficient way for a human to deal with it, but worth a go…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: