DEV Community

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

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. :)