1
$\begingroup$

For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements):

Let there be given $n$ elements $1,...,n$, a maximum weight $W$ as well as a weight & value function:
$w: \{1,...,n\}\to \mathbb{N}$
$v: \{1,...,n\}\to \mathbb{N}$
We then define $v^* = \max(v(1),...,v(n))$

The goal is to find a subset $M\subseteq \{1,...,n\}$ so that $\sum_{x\in M} w(x)\le W$ and so that $\sum_{x\in M} v(x)$ is maximal.
(I.e. we want to pack the subset of items that have the highest summed up value while not using up more weight than $W$)

I've been trying for quite some time, but I can't seem to come up with any idea or reduction rule that makes use of $v^*$.

Since this is a homework assignment, I'm looking for hints, not answers.


To be precise: The regular dynamic programming algorithm that solves the regular Knapsack problem can be used on this simplification as well (it might even be that the version given here is the standard version. The sources I've looked through so far don't say whether $w,v$ map to $\mathbb{R}$ or $\mathbb{N}$),
and find the optimal solution in $O(n\cdot W)$ time (see e.g. Wikipedia).

The algorithm variant I'm looking for however is independent of $W$, and instead uses the maximum value $v^*$ of any of the items.

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of Knapsack variant $\endgroup$ – Emanuele Nov 29 '18 at 19:39
  • 1
    $\begingroup$ @Emanuele How could this question be a duplicate of Knapsack variant? The accepted answer to that question reads "the best strategy you can do is just exhaustively try all possible choices". Here a pseudo-polynomial strategy is sought. $\endgroup$ – Apass.Jack Nov 30 '18 at 7:23
1
$\begingroup$

So, after eventually giving up on developing a different algorithm I looked back at the original solution, i.e. the one you can find e.g. on Wikipedia under 0/1 Knapsack problem.

The idea is to look closely at which fields of the table the algorithm builds are actually necessary, and which are not.

$\endgroup$

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.