Given an unordered list L of n numbers and a target value C, we want to find the

Question

Given an unordered list L of n numbers and a target value C, we want to find the smallest set (i.e. the set with the smallest number of values in the list) from the list whose sum is at least C. For example, suppose we have the following numbers: L = {1, 9, 8, 4, 6, 5} and C = 20, then we need to select at least three numbers (say 4, 8, 9) whose sum is 21 which is over 20, and thus is a good choice for C = 20. Now design an algorithm to find the smallest subset for the given list of numbers L and C. For simplicity, we may assume there is no duplicate numbers in L and all numbers in L are positive, and also C > 0. Your algorithm should run in O(n) time. Note: you cannot use hashing: hashing often works great in practice but they don’t have worst case run time as desired here. Also you cannot use linear time sorting algorithms such as counting sort: values of these numbers and C can be large. Hint: use the linear-time selection algorithm; and apply divide and conquer.

Explanation / Answer

In the standard selection algorithm, you take a random pivot and then look to see how many numbers fall on each side of it. You then either accept or reject one half, and keep working on the other half. You have just looked at each number in each half, in turn - the cost of each pivot stage is linear, but the amount of data considered at each stage reduces fast enough that the total cost is still only linear.

The cost of a pivot stage will still be only linear if you take the sum of all the numbers above the pivot. Using this, you can work out if accepting all these numbers, together with any numbers previously selected, would give you a collection of numbers that add up to at least K. If it does, you can ditch the other numbers and use the numbers above the pivot for the next pass. If it does not, you can accept all the numbers above the pivot, and use the numbers below the pivot for the next pass. As with the selection algorithm, the pivot itself and any ties give you a few special cases and the possibility of finding an exact answer early.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.