Recall the knapsack problem $($sometimes called the $0-1$ knapsack problem$)$: you are given n

items, where the ith item has weight wi and value vi $($both non$-$negative integers$),$ and a non$-$

negative weight capacity W of the knapsack. An optimal solution is a subset S $\{1,2,...,$ n$\}$

of the items having maximum total value

X

i in S

vi $,$

under the constraint that the total weight is at most the knapsack capacity, i$.$e$.,$

X

i in S

wi $<=$ W $.$

In this problem, we introduce the fractional variant of the knapsack problem, where one may

take any fraction pi in $[0,1]$ of any item i$.$ Naturally, a pi$-$fraction of item i weighs pi $$ wi$,$ and

has value pi $$ vi$.$ The goal is to maximize the total value of the selected fractional items.

$($a$)(3$ pts$)$ Briefly explain why the optimal value for the fractional knapsack problem is at least as large

as that of the original $0-1$ knapsack problem $($for the same weights, values, and knapsack

capacity$)$