2
$\begingroup$

The classic knapsack problem is maximize $P^T X$ subject to $W^T X\le M$ for $P, W\in \mathbb{R}^d$ and $M\in \mathbb{R}$ and $X\in \{0, 1\}^d$. Is there any research into algorithms that find the top $X_1, X_2, \cdots X_N$ such that $P_T X_1$, $P^T X_2, \cdots, P^T X_N$ are the top $N$ possible knapsack values subject to $W^T X_i\le M$ over all possible $X_i\in \{0, 1\}^d$? $X_1, X_2, \cdots , X_N$ need not necessarily be disjoint.

So when $W\in\mathbb{N}^d$, we have an efficient dynamic programming solution to the classic knapsack problem. Is there a similar dynamic programming solution when trying to determine the top $N$ knapsacks?

$\endgroup$
  • 1
    $\begingroup$ Have you tried adapting the DP solution to do what you want? $\endgroup$ – Raphael Sep 21 '15 at 7:37

Your Answer

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

Browse other questions tagged or ask your own question.