Trace the behavior of the fully polynomial-time TSP approximation scheme presented in Section 11.8 of Kleinberg & Tardos for the zero-one knapsack instance where n=9, the capacity is 60, and the weight sequence (wi) and the value sequence (vi) both equal (6,7,14,14,14,14,46,56,60), for both ε = 0.5 and ε = 0.25. Note that the optimal solutions are the one that includes only the item of weight 60, and the ones that include the item of weight 46 and an item of weight 14.

For each value of ε, give the items included and the scaled and unscaled value of the solution that the algorithm finds. For the tables, you only need to show those rows that correspond to values less than or equal to the scaled value of this solution. Do show how you obtained the included items from each table.