Categories
geek just life

mr. cook, we have a problem.

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) pj and a weight wj. 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, xj, is restricted to zero or one (for simplicity purposes).
  • mathematically the problem can be formulated as:
    maximize \sum_{j=1}^n p_j x_j.
    subject to \sum_{j=1}^n w_j x_j \le c, \quad \quad x_j = 0\;\mbox{or}\;1, \quad j=1,\dots,n.

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?