Knapsack problem

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.

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.

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.

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?

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.