Rajath Ramakrishna

Every day is a Knapsack problem

Posted on — | 3 min read

Knapsack problem, for those who don’t know, is an optimization problem that is encountered in several fields like computer science, investing, decision-making, etc. When defined in an abstract sense, the problem is to select a set of items each with a certain weight and value from a larger set such that the total weight does not exceed the volume of a sack. The problem is to optimize for the highest value that can be obtained through different combinations of the items. This can be done via several algorithms like greedy, dynamic programming, etc.

This is such a common problem in everyday life that we encounter is almost on a daily basis and lot of times we don’t even realize it. We just don’t name it as a knapsack problem. For example, a rock band that has a 1-hour time slot to play a bunch of songs must decide how many songs can they fit in that slot in order to provide the best experience possible. The 1-hour slot is a knapsack. Each song has a certain weight (duration) and value (popularity/crowd favorite/something else). A band can have one or more albums and the total number of songs in their arsenal far exceeds the 1-hour limit. With each song having a different value, they must choose a small set of songs very wisely so that they give the audience the best experience possible. This is one of the examples from the book Algorithms to Live By.

The knapsack problem I deal with on a daily basis is one of prioritization of tasks. There are a lot of things I want to get done - tasks I have to do at work, chores I have to do at home, work on a personal project and other one-off tasks I want to accomplish all in one day. I generally experience Dunning-Kruger effect where I over-estimate how much I can get done in a day but this happens only towards the end of the day and it becomes more of a realization of poor planning. However, whenever I stop and think about the day as a Knapsack Problem, prioritization becomes much clearer. The number of available hours in a day is the limit (sack), each task (item) has a certain value (in terms of urgency, importance or what I get back in return) and there are more tasks than I can fit in one day. Visualizing each day as a knapsack problem helps put things in perspective that there’s only so much I can do in a day that I must make the most out of it.

Once this is understood at a micro level at one day at a time, this can also be applied for longer time scales. But we are very inaccurate when it comes to forecasting far into the future. There are too many variables at play and we can’t predict with good enough accuracy as to what we can fit in the longer time scale and if it holds up until the end of that time scale. We can, to some extent, do this with bigger tasks like having to proritize a course we want to take that lasts a few months alongside a marathon we want to prep for, and a few other things we want to accomplish. But on a smaller timescale like a day, this works great.