| I read a paper on the knapsack problem about 8 years or so
ago at MIT. I think it was written by Rabin. This deals
with only one list of numbers.
Solution 1: Compute the 2^n sums until you find a correct
one. You don't have to compute the later sums after finding
an answer. Minimum space, 2^n worst case time, roughly half
that average time.
Solution 2: Separate the n integers into two groups of n/2
integers. For each of these, compute and store the 2^(n/2)
sums. Sort one list in ascending order, the other list in
descending order. Now run a pointer through each list from
beginning to end. If the sum of the current "semi sums" in
each list is too high, move the pointer in the descending
list to the next lower one. If the sum is too low, move the
pointer in the ascending list to the next larger one. When
the sum is just right, combine the two subsets and that is
your answer. Space proportional to twice 2^(n/2), time
proportional to 2^(n/2).
Solution 3: Sigh. This is the part that I cannot remember,
and haven't been able to reconstruct. But somehow he took
each of the two sets of n/2 numbers, split each into two
lists of n/4 numbers, computed the two lists of 2^(n/4) sums
from each "semi semi sum", and used these to generate the
sorted lists of solution 2. So the time was still roughly
2^(n/2) but the space was reduced from 2^(n/2) to 2^(n/4).
The paper made some comments about being able to move along
the Space^2 * Time = 2^n curve, but I don't remember those,
either.
Dan
|
| Hello.
I just joined Digital (I do not have a DTN and my e-mail is not stable).
I have a C code for solving the knapsack (again, you need to wait for a
few days until I get my files from my old system).
Since you have a 0-1 knapsack propblem, it is very easy to solve (I am not
sure of the size of the problem that you want to solve but the complexity
is W.n where W is the total capacity of the sack and n is the number of
objects. I use Dynamic Programming (which results in 10 lines of C code). There
are more sophisticated routines for solving such a problem. The DP approach
creates a table that has W rows and n columns. Each column represents an
object. At each stage (column), you have two possible decisions: not include
the current object or include it. If you do not include an object, you move
to the cell in the following column at the same height; i.e., the capacity
remaining is the same. If you include an object you move to a cell that is
w_i (where w_i is the weight of the current object) lower than the current
cell. Of course, you never go negative (that means the object cannot be
included). The cells in the table keep track of the value accumulated so far.
You start at 0, then whenever you add an object the value increases. To find
an optimal solution, look at the last stage, pick up the largest value and
trace back.
If you are interested in the code, please post (or try e-mail).
-Samer
[Posted by WWW Notes gateway]
|