Ask coding questions

← Back to all posts
Exact knapsack?
FlaminHotValdez (430)

So...A long time ago I did the classic knapsack problem.
The knapsack problem goes like this: You have a backpack or a knapsack that can only hold a certain weight. And you have a bunch of items that each have a certain weight and value. Now you want to put items into your backpack so that you can maximize the value. It's fine if you don't fill up the entire backpack and you still have space left. But I'm revisiting this problem, and I tried to make sure that you fit the backpack EXACTLY. You use EXACTLY all the weight in the backpack, no less, no more. My original solution doesn't work because it isn't optimized to conserve space, only to get the maximum value. Does anybody know the proper algorithm to do this kind of problem?

Comments
hotnewtop
Coder100 (16802)

that sometimes isn't possible
like:
each item has weight 3 and the backpack can hold 52 weight

FlaminHotValdez (430)

@Coder100 Yes, I am aware of that fact. Assuming that it is guaranteed to be possible, do you know a good algorithm to solve this?

Coder100 (16802)

@FlaminHotValdez yeah sure

1. sort it from biggest to smallest (also removing items greater than the capacity)
2. add items until you can't

so ez

FlaminHotValdez (430)

@Coder100 Small issue.

Let's say we have a backpack of size 9. We have 4 items, of size 7,5,4, and 3. Going by your algorithm, we only pick up the 7, but it's possible to pick up the 5 AND the 4, thus giving a better value.