[Scip] Using knapsack constraint in standalone solver

[Daniel Jensen]

Hello again,

I found a bit of time and coded up the brute force method I mentioned in 
my first email; this Java implementation finds the correct solution in 
around five seconds on my laptop. (Calling it "brute force" is probably 
misleading; if our knapsack has N items, only 2^(N/2) sums are 
considered out of the 2^N possibilities.)

This method takes O(2^(N/2)) space and up to O((N/2)2^(N/2)) time, 
while the usual DP algorithms take O(W) space and O(NW) time, where W is 
the weight limit for the knapsack. I imagine most real-world knapsack 
problems are better served by the DP algorithm, but for my problem, 
N/2=21 and getting sufficient precision to solve the problem required 
Log2[W] to be around 50 or more, so this method is a vast improvement.

It wouldn't take too much extra effort to convert this to C or to 
generalize it for the full-blown 0-1 knapsack (i.e. the case where the 
weights are not equal to the values), if folks are interested.

Beste Grüße,

Daniel
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ZeroOneKnapsack.java
Url: http://listserv.zib.de/mailman/private/scip/attachments/20110907/5d663ec0/ZeroOneKnapsack.ksh