The knapsack problem is as follows: given a set of integers S = {s1 , s2 , . . . , sn },

and a target number T , find a subset of S which adds up exactly to T . For example,

there exists a subset within S = {1, 2, 5, 9, 10} that adds up to T = 22 but not

T = 23.

Find counterexamples to each of the following algorithms for the knapsack problem.

That is, giving an S and T such that the subset is selected using the algorithm does

not leave the knapsack completely full, even though such a solution exists.

(a) Put the elements of S in the knapsack in left to right order if they fit, i.e. the

first-fit algorithm.

(b) Put the elements of S in the knapsack from smallest to largest, i.e. the best-fit

algorithm.

(c) Put the elements of S in the knapsack from largest to smallest.