6 ms·
Knapsack problem
- zura 13y agoThis is on of the mind opening problems. The whole dynamic programming is mind opening, I'd say.
- heroic 13y agoI and a colleague used Knapsack algorithm for a very interesting use case. You can find it here https://github.com/heroic/Rucksack https://github.com/heroic/Rucksack
- kba 13y agoThere is nothing new about the Knapsack problem. Why is this relevant?
- ambiate 13y agoDrawing huge state trees for the branch and bound solution to this problem was heart breaking on 40 minute exams.
- hackerboos 13y agoI 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.
- praptak 13y agoFun fact: some CD players could optimize the CD->audio cassette packing.
- ambrop7 13y agoI think that this would be an instance of the bin packing problem, not the knapsack problem ( http://en.wikipedia.org/wiki/Bin_packing_problem http://en.wikipedia.org/wiki/Bin_packing_problem ). (yes, the knapsack problem wikipedia page lists the bin packing problem as a generalization)
- adamgray 13y agoMe 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.
- leeoniya 13y agocombinatorics as the whole is quite interesting. i've done an implementation that arranges different fixed-dimension flooring panels into rooms of different sizes.
- itomatik 13y agoThat'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.pdf 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.
- leeoniya 13y agoit 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.
- itomatik 13y agonice! makes sense. I real life 'done is often better than perfect' =)
- bkanber 13y agoI wrote a tutorial on solving the knapsack problem with genetic algorithms in javascript a while back: http://burakkanber.com/blog/machine-learning-genetic-algorithms-in-javascript-part-2/ 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 13y agoI had to do this for an interview... in clojure. https://github.com/chadhietala/smuggler https://github.com/chadhietala/smuggler
- IgorPartola 13y agoIn 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?
- praptak 13y agoThis 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.
- itomatik 13y agoCan 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 13y agoKnapsack! 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.
- itomatik 13y agoHold 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?
- itomatik 13y agoIn which context were you solving this problem? I'm trying to optimize products distribution.