Sweat trickled from my forehead. It was 5:00 a.m. Monday morning – the end of last year’s Spring break.
Before a University of Florida break, I spend a few minutes jamming all of my homework, upcoming exams, and fun activities into a makeshift To-Do-List. I always returned to campus with none of these things accomplished, until I started thinking of the process of making a To-Do-List as a solvable Knapsack problem.
A Knapsack problem goes something like this: a NY-bound traveler can only bring a small knapsack along, due to new airline rules. The traveler was going to bring food, water, eight sets of clothes, toiletries, a laptop, a cell phone, magazines, a cat, jewelry, a hammer, and other things, but not everything will fit in the knapsack.
If I don’t make a to-do-list, I tend to forget things. I’ve missed deadlines because I didn’t add them to my calendar, gotten many “Why did you ignore my text?” texts, and almost stood somebody up on a date, once.
For the NY-bound traveler, not packing could kill. If his or her plane crashes in the ocean, he or she is the only survivor, and nobody packed food, he or she could starve.
In the past, I made my To-Do-List without thinking. I skimmed through my crumpled notebooks, looking for underlined words, and randomly typed them into the Mac OS X Notes application.
In the crash scenario, an unorganized packer might have packed reading magazines instead of peanut butter. Or perhaps diamond earrings instead of bottled water.
A dream To-Do-List, like a dream knapsack, should include different things based on their importance and when they’re needed. Studying for an exam that’s a month away can happen later, but finishing the online assignment due in 30 minutes could be the difference between getting an A and an A- in a course.
The Knapsack problem is called an optimization problem. There are different resources – available choices – that need to be allocated, or used up, optimally - in best way possible.
Some optimization problems have answers, but they can’t be found in a human lifetime. In the Traveling Salesman problem, a delivery truck driver might want to find the fastest route from a warehouse, to a billion cities, and back to the warehouse without visiting the same city twice.
The Traveling Salesman problem has an almost-optimal answer companies use to save money. If the knapsack is twice as big as the Eiffel Tower, a computer can find an almost-optimal answer to the Knapsack problem in seconds.
This might be a waste of time, but thinking of making a To-Do-List as packing a knapsack, I might make a list I’ll follow through on. The resources I have to allocate optimally are the tasks, which each have a different importance.
I’m going to make a To-Do-List with at most 5 tasks. Since it’s relatively small, I don’t need to type stuff into a computer program with dynamic programming, a way to break big problems into smaller pieces.
Instead, I’ll dumbly try all possible combinations of tasks on my To-Do-List and pick the combination that has the most stuff inside. I’m going to say my To-Do-List can weigh at most 25.
A rule from mathematical combinatorics says if there are 5 different tasks, there are 32 different ways to combine them. I can put none of the tasks on the list, or the first 3, for example.
I’ll give each of my tasks a different weight, on a scale from 1 to 10. If I add up all the tasks on my list, they weigh 30 units – which are more than 25, the maximum weight.
So I check the other 31 combinations. I could go to the beach, study, make a blog, and return to the beach – but skip grocery shopping for 24 units.
Some choices, like only going to the beach for 10 units, don’t make sense – trying all the different combinations brought this to light. It’ll take a few extra minutes, but at the end, I'll have an optimal To-Do-List full of important things I will accomplish.
I hope everyone is busy enjoying the sunshine – or darkness – this Spring break. Maybe somebody will find this blog useful.
Or not. At least I can check something off my list.