Knapsack problem(en.wikipedia.org)
en.wikipedia.org
Knapsack problem
http://en.wikipedia.org/wiki/Knapsack_problem
20 comments
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)
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.
Fun fact: some CD players could optimize the CD->audio cassette packing.
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.
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.
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.
Now the problem is to find bags types and corresponding amounts such that total cost is maximized.
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.
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?
In which context were you solving this problem? I'm trying to optimize products distribution.
This is on of the mind opening problems. The whole dynamic programming is mind opening, I'd say.
Drawing huge state trees for the branch and bound solution to this problem was heart breaking on 40 minute exams.
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?
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.
I and a colleague used Knapsack algorithm for a very interesting use case. You can find it here https://github.com/heroic/Rucksack
I had to do this for an interview... in clojure. https://github.com/chadhietala/smuggler
combinatorics as the whole is quite interesting. i've done an implementation that arranges different fixed-dimension flooring panels into rooms of different sizes.
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.
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.
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.
nice! makes sense. I real life 'done is often better than perfect' =)
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.