📈 #27 (Microsoft's) Knapsack Problem

Will this smart backpack solve the knapsack optimization problem?

The other day I was reading a news article about Microsoft's new smart backpack¹.

Yes, they've already patented it, just in case.

The truth is that it's amazing: it integrates Artificial Intelligence, can identify objects around you, access information, and even interact with other devices. And to do this, it uses a camera, microphone, speaker, and processor to analyze its surroundings and respond to your voice commands 👏🏻

But when I go traveling, what I want to know is how to pack my clothes in it without leaving anything important behind. Mind you, it's not a trivial problem; I need to understand the benefit of packing each pair of pants, shirt, and sweatshirt, knowing that it will take up space where no other garment can fit.

Will Microsoft's new smart backpack be able to solve this problem?

I don't know, but what I do know is that it's a very interesting optimization problem, and in this edition of Factibles I tell you about:

• What this problem is

• Its computational complexity

• An example of solving it on Google Sheets

• Its real-life applications and problem variants

Let's go for it!

Do you remember when I told you about my trip to Vietnam and how we organized the trip?

What I didn't tell you at the time is that I only carried a backpack with everything necessary: clothes for a week (even though I was there for two), personal hygiene accessories, and the usual mobile charger, Kindle, tablet…

But I wasn't quite sure what weather I would encounter. It was August, so it was definitely going to be hot, but in the rice terraces of Sa Pa, which are in the north of the country and in a very mountainous area, there's a lot of humidity and it could get cold at night. So, I wasn't very clear on what to pack. Mostly summer clothes, even a swimsuit in case we went to the pool or the beach (which we did), but also some light warm clothing.

I'm sure you've experienced something similar.

The problem is that you're not quite sure what to pack. If you include a pair of long pants, a couple of sweatshirts for those cold days, and a light jacket with a hood in case it rains, it weighs more and takes up a lot of space in the backpack, forcing you to reduce the summer clothes, depriving you of the chance to wear those shorts you just bought. You have to balance the situation and make a decision.

And I don't know about you, but I see this as an optimization problem, right? On one hand, you have the backpack, a limited space with a maximum weight you can carry, and on the other, you have the clothes you want to pack with the goal of enjoying your trip to the fullest. Welcome then to…