Dynamic programming for Knapsack problem

Question

So in the second part of an exercise I am given a specific Knapsack problem that is supposed to be solved using dynamic programming which is not that difficult but it is also mentioned to use part (a) which is defined as follows

Let

$$f(\lambda) = \max\{\sum_{j=1}^nc_jx_j : \sum_{j=1}^nw_jx_j \le \lambda\}$$ $$q(t) = \min\{\sum_{j=1}^nw_jx_j : \sum_{j=1}^nc_jx_j \ge t\}$$.

Show that

• $f(\lambda) \ge t \iff q(t) \le \lambda$
• $f(b) = \max\{t : q(t) \le b\}.$

I tried to play around with f and q but couldn't find any relation even though it seems kind of obvious. Also I see no way to apply this to part (b).

Any hint would be highly appreciated.

Answer 1

For a given $\lambda$, look at the $x$ that yields the value $f(\lambda)$ and see what happens when you plug that $x$ into the expression for $q()$. Repeat in the other direction.

As for applying this to the other part of the problem, perhaps the "dual" of the problem you were originally given to solve is somehow easier?