Question

We have a bag which has a weight capacity of x kilograms. We also have n
items, each of different weights. Our target is to pack as many items as possible in
the bag, without exceeding the weight capacity. Note that, we want to maximize
the number of items, not the total weights of the items. Design an algorithm to
determine the desired items in O(n) time.

Answer 1

We assume w[] is the array of weights sorted in ascending order and subscripted from 0 to n-1.

ALGORITHM:

1. We input x, n and w[].

2. We set bag to empty, i to 0 and wCurr to 0.

3. We repeat steps 4 and 5 till i<n.

4. If wCurr+w[i]<=x, we add the ith item to the bag, make wCurr=wCurr+w[i] and increment i by 1.

5. Else we go to step 6.

6. We output the bag, wCurr and i. wCurr is the weight of the bag, and i is the number of items in the bag.

In its worst case, it will go through all the items, i.e., a time complexity of O(n).