when i failed to join the air force and had to choose another career, i picked informatics, journalism and astronomy, all in the same application form – that’s how clueless i was towards my future. in the end, informatics won, and 7 years later, here i am, still clueless but with an engineering degree! :)
every now and then, on the most improbable situations, the informatics/mathematics part comes in handy, like for instance (and ironically) when i have to fly.

here’s the formal definition of a common problem, known as packing. the next time your mom tells you to stop procrastinating on your packing duties, you can properly explain her how hard that is – and hopefully delay the task a little longer!

• you have n kinds of items, 1 through n. each item j has a value (sentimental or of importance) p_j and a weight w_j. the maximum weight one can carry in the suitcase is c, and according to british airways, c=23 kgs.
• the number of each kind of item in the suitcase, x_j, is restricted to zero or one (for simplicity purposes).
• mathematically the problem can be formulated as:
  maximize
  subject to

this is called a 0-1-knapsack problem, which is known to be a np-complete problem. np stands for non-deterministic polynomial time… and that translates into “very hard & time-consuming problem”.

another np-complete problem is called bin packing, which consists of neatly placing different volumes in as less bins as possible. no time-efficient solution has been discovered for these problems.

so there you go. combine the two and you have packing! :D

(and now, back to the suitcases…)

ps – images from wikipedia, more on the subject here.
ps2 – who was stephen cook?