Knapsack Problem

This assignment develops a two approximation algorithms for the Knapsack problem, defined

as follows. There is a set of $n$ items and knapsack that can hold a maximum weight of $W.$

Item i has value $v_i$ and weight $w_i.$ The goal is select a subset of items with maximum total

value subject to the constraint that their total weight is at most $W.$

There are dynamic programing algorithms for knapsack that run in $O(nW)$ and $O(nV)$

time, where $V={\displaystyle \underset{i}{\overset{?}{}}}{v}_i.$ These algorithms are pseduo$-$polynomial because the inputs to the

problem can be expressed in $logW$ space. Therefore, $O(nW)$ is actually exponential in the

input size! In fact, we can show the knapsack problem is NP$-$hard $($for example from the

partition problem$).$

For any subset of items $S,$ it will be convenient to define $V(S)={\displaystyle \underset{\text{i}\text{i}\text{n}\text{S}}{\overset{?}{}}}{v}_i,$ as the value

of $S,$ and $W(S)={\displaystyle \underset{\text{t}\text{i}\text{n}\text{S}}{\overset{?}{}}}{w}_i,$ as the weight.

Problem $1$

A natural greedy strategy is to rank the items by 'how good they are' $($as measured by the

ratio of value to weight $\frac{v_i}{w_i})$ and pick items in decreasing order until the knapsack is filled.

Greedy

Sort and relabel items so that $\frac{v_1}{w_1}\frac{v_2}{w_2}$cdots$\frac{v_n}{w_n}.$

Take the largest subset $\{1$dotsk$\}$ that fits in the knapsack, ${\displaystyle \underset{t=1}{\overset{k}{}}}{w}_{k}W.$

ModifiedGreedy

Return max$($output of Greedy, highest valued item$)$

a$)$ Provide an example input where Greedy ~~$OP\frac{?}{W}.$ You don't need to assume that

$v_i\text{'}$s and $w_i\text{'}$s are integers.

b$)$ Suppose that Greedy takes the first $k$ items $\{1,$dots,$k\}.$ Prove that

${\displaystyle \underset{i=1}{\overset{k+1}{}}}{v}_i>$OPT,

note that this bound takes one additional item $v_{k+1}.$