# knapsack problem ?

• 01-26-2011
nmt1402
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.
• 01-26-2011
carrotcake1029
Give it an attempt, and we can help you if you run into any problems.

Please see the homework policy:
C Board - Announcements in Forum : General Programming Boards