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

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