How to get top-x elements that result in a specific sum

user_11597907 0
Viewed 278

I would like to get the top X elements of an array that sum-up to at least a given sum without sorting the whole array beforehand in linear time. I think its not possible to get linear time in all cases but at least in my input arrays i have roughly 1% of the elements that make out 99% of the sum. And i need to identify those correctly. I don't know know if it helps but the sum of all elements is always 1.

I have already implemented it with a sorted array but that blows up the complexity of my algorithm. Afterwards I have already looked into the top-k algorithm and the knapsack algorithm but they do not allow a flexible x elements dependet on a given minimum sum. 

Input Array: [0.1, 0.2, 0.4, 0.05, 0.01, 0.01, 0.01, 0.02, 0.15, 0.05]

Example 1:

Given Sum: 0.8

Expected output [0.1, 0.2, 0.4, 0.15, ] --> Sum 0.85 but only top 4 elements

Example 2: 

Given Sum: 0.95

Expected output [0.1, 0.2, 0.4, 0.15, 0.05, 0.05 ] --> Sum 0.95 but only top 6 elements

Really looking forward to your answers!

knapsack-problem arrays algorithm python
2 Answers

If we can have a median selection algorithm with good enough likelihood that its time complexity is O(n), then we can have overall O(n). Observe that after selecting the median we only need to examine one of the parts in the partition, leading to N + N/2 + N/4... with a bound of O(n). This is because the wanted sum is either contained in the half above the median or we need to add more from the lower half, in which case we need not examine the upper half.

user_20347870

You can round your values to say 3 decimal digits, and use the bucket sort. With 3 decimal digits, you will need 1000 buckets. You may use more or fewer buckets depending on your problem. The time complexity will be O(n+k) where k is number of buckets.

In your buckets, you can store the exact values, and so when scanning the buckets to get the desired sum, you would use the actual values. You said the top values usually represent 1% of all values. The top buckets should then contain only a few values.

user_38263870
Related