Greedy Can Fail Badly Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;valuesv1,,yn∈Z+； knapsack capacity B E+; Find an S)that maximizes s subject to∑icsM≤B. Greedy Fit: Sort items non-decreasingly in v:/w; scan items one-by-one in that order,for each item: include the item in the knapsack if it fits; approximation ratio:arbitrarily badGreedy Can Fail Badly Instance: items ; weights ; values ; knapsack capacity ; Find an that maximizes subject to . n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ S ⊆ {1,…, n} ∑i∈S vi ∑i∈S wi ≤ B Greedy Fit: Sort items non-decreasingly in ; scan items one-by-one in that order, for each item: include the item in the knapsack if it fits; vi/wi approximation ratio: arbitrarily bad