Benjamin DeHass | San Jose, CA
I recently just moved across the country to begin a new chapter this year, and one of the biggest problems I faced was getting my things there with me. I was limited to the backpack and suitcase I flew with, alongside 125 lbs of things that could go in my car (per the shipping company). These constraints were tight, as I had to pack clothes, electronics, linens, toiletries, and a host of other possessions in that limited capacity. This is the nature of The Knapsack Problem (specifically a multiple knapsack problem).
In the knapsack problem, you have a bag that can carry at most weight W and N total items. Each item has a value vi and a weight wi. The objective function is that of maximizing the value while adhering to the weight limit. The sum of the weight of items placed in the bag may not exceed W.
Returning to the moving dilemma, my total carrying weight allowed was W = 125 (car) + 50 (suitcase limit on airlines) + backpack (25 for sake example). The objective function is to maximize the value of things I bring with me to start my new work experience across the country. These items can weigh no more than 200 lbs collectively, and since the problem is generally a 0/1 Knapsack Problem, items cannot be brought fractionally in most cases. The value of items is largely based on how irreplaceable they are (phone, laptop are high, socks are low), as well as cost and necessity for day to day tasks.
I wasn’t just packing up to move, I was running an algorithm. This site, Art of Optimization, is my journey to find optimization in everyday tasks, to help myself and others to reduce inefficiency in areas worth optimizing, and to help recognize and distinguish between tasks that require an algorithm and the moments where no optimal path is what makes them worth living.