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.
