Side Note Please explain the answer as you go if you can so

Side Note: Please explain the answer as you go if you can, so I can understand it too.

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, suppose S = {1, 2, 5, 9, 10}. Then the subset {1, 2, 9, 10} adds up to T = 22, but there is not a subset that adds up to T = 23. Subsets of S that add up to T are considered full-knapsack solutions.

1 Find counterexamples for each of the following algorithms for the knapsack problem. That is, given S and T, the algorithm does not find a solution which leaves the knapsack completely full, even though a full-knapsack 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.

Note: A complete solution for parts (a-c) consists of the following.

• You must specify a set S of integers. • You must specify a target number T.

• Give a full-knapsack solution based on your set S and target T.

• Apply the given knapsack algorithm on the set S and target T and show why it will not produce a full knapsack solution.

Solution

(a) and (b) S = {1,2,5,9,10} and T = 11

By the best-fit algorithm it will choose {1,2,5} which add up only to 8 but if we choose {9,2} it will give the target solution, so best-fit algorithm will not necessary give correct solution. same for first-fit algorithm

(c) S = {1,2,5,9,10} and T = 14

By the algorithm largest to smallest it will first choose 10, then 2 and at last 1 which add up to only 13{10,2,1} but required target is 14 but if we choose 9 and 5 it will add up to 14 {9,5}. Hence algorithm will not always give correct solution.