0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Should I post on Stack Overflow instead? $\endgroup$ – Tzu Tau May 12 at 12:26
0
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So in other words, it's equivalent that, for each possible weight (not each $w < W$, but that a subset could possibly be), store indices of the subsets with greatest value by comparing the previous one recorded subset and the new subset, then no need for extra search after locating the subset with greatest permissible weight. Is that correct (maybe my description is a little twister)? $\endgroup$ – Tzu Tau May 12 at 14:10
  • $\begingroup$ yes, that's correct $\endgroup$ – Matt Timmermans May 12 at 14:27
  • $\begingroup$ Thanks you very much! $\endgroup$ – Tzu Tau May 12 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.