Recall that in the $0-1$ knapsack problem, you are given n items, where the ith item has

weight wi and value vi $($both positive$),$ and a non$-$negative weight capacity C of the knapsack.

An optimal solution is a subset S $\{1,2,...,$ n$\}$ of the items having maximum total value