DEV Community

Cover image for Knapsack problem algorithms for my real-life carry-on knapsack

Knapsack problem algorithms for my real-life carry-on knapsack

Victoria Drake on May 11, 2018

The knapsack problem I'm a nomad and live out of one carry-on bag. This means that the total weight of all my worldly possessions must f...
Collapse
 
patricktingen profile image
Patrick Tingen

Love your post, great read!

One suggestion for your calculation though. If it is that important to bring your laptop (and the cable and charger off course) then why bring them into the calculation at all? Same might apply to some other items that you do not want to travel without, like underwear. By giving it a value that is greater than the sum of all other items, you are basically trying to beat the algorithm. Just leave them out and lower the target weight by the weight of the items you want to take with you anyway. This will - as a bonus - even simplify the problem and thus further lower execution time.

Collapse
 
falansari profile image
Ash

Yep, this. I was going to comment about items that change in importance based on destination. For example, her gloves are not showing up in the results set, however they're mandatory if she's going to a very cold country! Her sunglasses on the other hand are always present, yet they're not that necessary if she's going to the UK ;) your approach fixes these issues of "must have items for this trip"

Collapse
 
victoria profile image
Victoria Drake

In short, yes. To carry the analogy through I left all the items in, but as a practical exercise, removing the mandatory ones from the calculation makes more sense. :)

Collapse
 
rhymes profile image
rhymes

Thanks for this! It blew my mind.

On a separate note: I've been circling around Minaal Carry-on 2.0's website, read your review and watched a couple of YT videos about it. Paradoxically, not being a digital nomad, I haven't decided to get it yet because I already own too much stuff, unsatisfactory bags included :D

Collapse
 
victoria profile image
Victoria Drake

I went through a few iterations to find the ideal feature set before I settled on this bag. I'm basically a human algorithm really.

YMMV. It helps to get a few hundred km of travel under your belt (with any bag) so that you have enough personal experience to decide on the features that are important to you.

Collapse
 
rhymes profile image
rhymes

YMMV. It helps to get a few hundred km of travel under your belt (with any bag) so that you have enough personal experience to decide on the features that are important to you.

Yeah I agree.

I love your blog! Thanks again :-)

Collapse
 
shriharshmishra profile image
Shriharsh

Great article! introduced me to dynamic programming.

Sorry to be nitpicking - rows and columns should be interchanged in this statement -

"Create a matrix representing all subsets of the items (the solution space) with columns representing items and rows representing the bag's remaining weight capacity"

Collapse
 
victoria profile image
Victoria Drake

Congratulations, you've passed the secret hidden test and won a prize!

Seriously though good catch! I must have missed that several times. Guess you're the only one who read the article. :)

Thank you!

Collapse
 
shriharshmishra profile image
Shriharsh

The topic was dense to me and I am unknown to Go syntax, so I was reading slowing over several days and thinking about it :P

Collapse
 
ben profile image
Ben Halpern

Oh my goodness this is thorough. Fascinating post Vicky!

Collapse
 
victoria profile image
Victoria Drake

Yeah, I really tried to pack in as much info as I could!

... notsorry.

Collapse
 
ben profile image
Ben Halpern

Collapse
 
jarsen profile image
Jason Larsen

Love this writeup! I've been wanting to revisit some of my college algorithm days in Go, this has gotten me excited to do it :)

Collapse
 
dfeuster profile image
Daniel Feuster

Great article! It connected some dots for me, very thorough. Thank you.

Collapse
 
victoria profile image
Victoria Drake

You're welcome Daniel! I'm very glad you found it useful!

Collapse
 
jibinp profile image
Jibin Philipose

Wowwwww

Collapse
 
nestedsoftware profile image
Nested Software • Edited

As a note, I believe this problem is np hard in the general sense, so I don’t think trying all the combinations by brute force would normally scale very well. I’m not sure when it breaks down though.

Collapse
 
nestedsoftware profile image
Nested Software

This is a bit trickier than I originally thought. The problem is “weakly” np hard. See en.m.wikipedia.org/wiki/Weak_NP-co... for more details.