knapsack problem ?
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.
