Question

2. Suppose you have a collection of n items i1, i2, ..., in with weights w1, w2, ..., wn and a bag with capacity W

(a) Describe a simple, efficient algorithm to select as many items as possible to fit inside the bag e.g. the maximum cardinality set of items that have weights that sum to at most W.

(b) Prove your answer.

Answer 1

a) Algorithm:

i) sort in increasing order: ;

ii) set ;

while and ,

if then and

iii) return .

Analsysis: Step i) requires (via Quicksort) steps, and step ii) requires steps. Thus, the time complexity of our algorithm is which shows it is effective (polynomial time).

Note: The design of the algorithm mandates that

b) We need to prove that if is any algorithm and returns , then .

Proof: Suppose, if possible, that . Because of step i), we have

Thus, we have

which is a contradiction. Thus, , completing the proof.