Knapsack problem

http://en.wikipedia.org/wiki/Knapsack_problem

by groundCode • 13 years ago

31 19 13 years ago

en.wikipedia.org

zura• 13 years ago

This is on of the mind opening problems. The whole dynamic programming is mind opening, I'd say.

heroic• 13 years ago

I and a colleague used Knapsack algorithm for a very interesting use case. You can find it here https://github.com/heroic/Rucksack

ambiate• 13 years ago

Drawing huge state trees for the branch and bound solution to this problem was heart breaking on 40 minute exams.

hackerboos• 13 years ago

I studied if for my university dissertation.

It's easy to think of practical applications, example - I have a folder of videos/mp3s etc and I want to fit them on a few DVD-Rs. This algorithm can calculate the most efficient way of getting the most data on the disk without splitting files.

praptak2• 13 years ago

Fun fact: some CD players could optimize the CD->audio cassette packing.

ambrop7• 13 years ago

I think that this would be an instance of the bin packing problem, not the knapsack problem ( http://en.wikipedia.org/wiki/Bin_packing_problem ). (yes, the knapsack problem wikipedia page lists the bin packing problem as a generalization)

adamgray• 13 years ago

Me too! I compared general purpose GPU libraries versus performance on a Beowulf cluster and OpenMP / UPC. Was a lot of fun and an interesting experience.

leeoniya2• 13 years ago

combinatorics as the whole is quite interesting. i've done an implementation that arranges different fixed-dimension flooring panels into rooms of different sizes.

itomatik5• 13 years ago

That's pretty cool. It's actually non-trivial problem. Did you write some sort smart bruteforce? Or you had figured some DP approach? There was a simplified version of it on IOI 2004 (http://olympiads.win.tue.nl/ioi/ioi2004/contest/day2/phidias...) which asked to cut the room by a series of horizontal and vertical cuts. At the end each of remainder blocks can either be fully covered by predefined set of fixed-dimension panels or thrown away. The problem asked to minimize what we throw away. It was solvable using DP due to the fact that cuts are always split the room into separate parts.

leeoniya2• 13 years ago

it was not DP, but worked quite well, because some of the conditions were eased. the product quantity was unlimited, so as many products as needed could be used. we basically needed to fill the space with as few products (thus dimensionally larger) as possible to minimize the installation work.

it ended up starting out greedy, taking large panels first and adaptively backtracking when the current size could not be placed. if by the end of the iteration we did not reach a minimum coverage area, we would backtrack and remove the last significant size panel and fill it with smaller ones. it didnt get us the "optimal" solution but it was fast and more than sufficient.

bkanber• 13 years ago

I wrote a tutorial on solving the knapsack problem with genetic algorithms in javascript a while back:

http://burakkanber.com/blog/machine-learning-genetic-algorit...

There are better ways to solve this problem, of course, but the primary goal was to talk about GAs, not to solve the knapsack problem in the most efficient manner.

chadhietala• 13 years ago

I had to do this for an interview... in clojure. https://github.com/chadhietala/smuggler

IgorPartola• 13 years ago

In the little example they give on the side, why not sort all items by value density, high to low, then fit items until the knapsack is full? Not so simple for multiple dimensions, but when does this not work in a single dimension case?

praptak2• 13 years ago

This greedy approach is in fact the basis for an approximation algorithm with a guaranteed ratio aproximation. Failure to reach optimum: 110 dollars 55 volume gets chosen over 2*(60 dollars 50 volume), assuming knapsack volume 100.

itomatik5• 13 years ago

Can somebody tell me if the following problem is solvable using knapsack (so far I've been only able to come up with bruteforce solution with some optimizations): We have different product types and for each product know it's amount. Let's say we have 20 different product types. For each type we know how much we've got (i.e. 10k of product type 1, 15k of product type 2, etc.) Now we want to put those products into different bags. Each bag must have 5 products. A particular combination of products inside of the bag is considered a "bag type". If we choose a particular "bag type" we must to have at least 7,500 units of such bag type. For each bag type we have a certain cost function.

Now the problem is to find bags types and corresponding amounts such that total cost is maximized.

danielovich• 13 years ago

Knapsack! And there is no way to determine the best solution before every combinations has been tried. I have been in the exact same spot as you but ended up making a specific module for it which didn't needed any computation beforehand.

itomatik5• 13 years ago

Hold on, so you did you bruteforce all-all possible solutions and then just picked the best one out of them? How many products you had? Was it close to what I have? In my case there are just too many possible solution. I waited for an hour on my current one and it didn't finish :) What was your strategy with regards of how much each bag type you select? Try all possible from current_max downto 7,500?

itomatik5• 13 years ago

In which context were you solving this problem? I'm trying to optimize products distribution.

Knapsack problem

Related Stories