I've been playing around with Go a lot the past year. I've done a couple of projects for pay, and a couple of projects for fun. I have been finding it an incredibly useful pocket language for solving almost any problem.
Recently, I spent some time researching the different solutions to the knapsack problem. After reading all about the knapsack problem on wikipedia, I implemented the bounded solutions in go. As a control, I used the item list for Nils Haldenwang's post about Genetic Algorithm vs. 0-1-KNAPSACK.
I started off with a recursive brute force approach, and kept evolving that approach until I had an iterative solution that used a channel for generating the set of combinations. It probably isn't the most efficient way to implement the set generation, but I still tend to throw channels and goroutines at any generator I see in code.
After I had the brute force approach, I optimized it a little bit by trimming out branches that would never be used. This resulted in about half the time required for the same dataset. But it actually doesn't change the worst case scenario much. It isn't so much of a solution as an optimization that makes it look a little more breadth first search. These ran in about 17 seconds for brute force, and 12 seconds for the optimized version.
Then I implemented the dynamic programming approach, which is just unbeatable speed wise. Didn't even register as a millisecond for the testing dataset. It took me a little bit to understand how to discover the list of items packed in the knapsack, but the total solution was still small enough to understand. I used Mike's Coderama to help me understand what was going on there.
Finally, I implemented the meet in the middle solution. This was actually a surprisingly faster solution than I expected. The code was able to reuse the parts I had done for the brute force solution, which made it fast to write. The simple solution was able to solve the 24 item problem in about 100ms. I played around with it a bit to optimize the best-case scenarios, and got it to about 40ms on average.
In the end, I like the meet in the middle solution the best. It is feasible to use the solution for all types of bounded knapsack problems where you have to use a float for the weight. I posted my go implementation of the bounded knapsack problem on gist.
Now, its time to play with the bin packing problem.