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
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?