-3

Given a set of n elements x > 0 and a weight W. Find the minimum of elements needed that sum up to W or greater. I am struggling to find a linear time (O(n)) algorithm.

[Edit: Linear sorting algorithm cannot be used her since all values are rationals (also distinct rationals)]

lukas
  • 1
  • 1
  • Check [this](https://stackoverflow.com/questions/5963983/find-the-minimum-number-of-elements-required-so-that-their-sum-equals-or-exceeds) link. Your question has been already answered. – jennifer lawrence Oct 29 '18 at 15:04
  • 1
    Possible duplicate of [Find the minimum number of elements required so that their sum equals or exceeds S](https://stackoverflow.com/questions/5963983/find-the-minimum-number-of-elements-required-so-that-their-sum-equals-or-exceeds) – ruakh Oct 29 '18 at 15:30

1 Answers1

1

Firstly you need to sort these elements. And then you can easily find the minimum number of elements in linear time. You need to go from the largest element to the smallest and sum them up as long as this sum <= W.

The usual sorting algorithm takes O(n*log(n)). So you need an algorithm for sorting numbers in linear time. If you have a set of integers, you can use one of these algorithms http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap09.htm

Multifora
  • 133
  • 1
  • 10