How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack?

Question

I am now studying Knapsack Problem (KP), and find the Meet-in-the-middle algorithm described in Wikipedia a little unclear that, how to realize it in the theoretical time complexity of $O^*(2^{n/2})$? I can understand the algorithm for Subset Sum Problem (SSP) which is a particular instance of 0-1 KP, but for the generalized problem there might be something wrong with the step:

  for each subset of A do
      find the subset of B of greatest value such that the combined weight is less than W

As I understand, this is to search (eg. do binary search) on combined weights of all subsets of B, which takes logarithm time for each search. But after knowing which subsets have combined weight less than W, how to find the one of greatest value? If search on values of the subsets with weight < W, it takes linear time to find the maximum since the list of value is unsorted this time. As a result, the total time complexity is no longer $O^*(2^{n/2})$, but something like $O^*(2^n)$.

Even if it starts from finding the subset of greatest value (easy for a table) first without constriction on combined weight, after that, verification of weight will probably turn false and thus more tests are needed for other subsets, of which the number seems associated to the table size linearly again.

Now I can only assume the total value and combined weight are strongly positive correlated, so that after finding the subset with maximum allowed weight, it takes only constant time to search around this subset for the exact one of greatest value. But I am not satisfied with this explanation. So anyone has better ideas about this issue?

PS: I have read the original paper by Horowitz, Ellis and Sahni, Sartaj, but I found the problem defined there is a decision problem rather than the common optimization problem. Maybe somebody can provide ideas in this direction.

Answer 1

First, precompute the weights of every subset of $B$.

Sort them by weight and put the weights and subsets in parallel arrays so that $W[i] = weight$ and $S[i] = subset$.

Then make another parallel array so that $BEST[i]$ is the index $j$ of the set of greatest value such that $j<=i$. You can do this with a single scan from $i=0$ upward, remembering the greatest value seen so far at every step.

Now, to search $B$, you do a binary search in $W$ to find the maximum permissible weight, and get the best set from the same index in $BEST$