The 0-1 knapsack problem is defined as follows:

A thief robbing a store finds [tex]n[/tex] items. The [tex]i^{th}[/tex] item is worth [tex]v_i[/tex] dollars and weighs [tex]w_i[/tex] kilos, with [tex]i[/tex] and [tex]w_i[/tex] as positive integers. The thief wants to take as valuable a load as possible, but he can carry at most [tex]W[/tex] kilos in his knapsack, where [tex]W > 0[/tex]. Which items should he take to maximize his loot?

This is called the 0-1 knapsack problem because for each item, the thief must either take it or leave it behind; he cannot take a fractional amount of an item or take an item more than once.

In the fractional knapsack problem, the setup is the same, but the thief can take fractions of items, rather than making a binary (0-1) choice for each item. After some deep thinking, the lecturer of COMP333 proposes the following modeling for the fractional knapsack problem:

Let [tex]S = \{1, 2, \ldots, n\}[/tex]

[tex]\text{Opt}(S, W) = \max_{1 \leq j \leq n, 0 \leq p \leq 1} (p \cdot v_j + \text{Opt}(S \setminus \{j\}, W - p \cdot w_j))[/tex]

and [tex]\text{Opt}(\emptyset, W) = 0[/tex].

Notice that the 0-1 knapsack problem is a particular case where [tex]p[/tex] must be either 0 or 1.

1. Prove that the fractional knapsack problem recursive solution defined by the equation has an optimal substructure. Can you reuse your previous proof to prove that the 0-1 knapsack problem has an optimal substructure? If yes, you should show why; if not, provide an alternative proof.

2. A greedy strategy for the fractional knapsack problem is to pick up as much as possible of the item that has the greatest possible value per kilo. Assume we first compute the value per kilo for each item, i.e., [tex]v_i = \frac{v_i}{w_i}[/tex]. The greedy choice for [tex]\text{Opt}(S, W)[/tex] is to take as much as we can of item [tex]i \in S[/tex] where [tex]v_i[/tex] is maximal. Show that the previous greedy choice yields an optimal solution for the fractional knapsack problem.

Consider the following concrete instance of the knapsack problem: The maximum capacity of the knapsack is 80, and the 4 items are as follows. Compute the optimal value for the fractional version using the greedy algorithm.