Splitting an array into subarrys so that we have minimum number of subarrays with sum of elements < k

Asked Apr 09 '19 at 22:23

Active Apr 09 '19 at 22:27

Viewed 243 times

I have an array with the following elements:
a <- c(2, 2.99, 3.95, 3, 2, 2, 2, 9.95, 9, 16.89, 8.99, 15, 15, 15, 14, 14, 16.14, 16.14, 16.14, 15.14)

I'm looking for a way to split this array into the minimum number of subarrays such that the sum of values within each subarray is less than 20.
I tried to solve this by sorting them in ascending order and starting by grouping smaller values first, but I don't think that is the best (or accurate) way to solve this.

edited Apr 09 '19 at 22:27

asked Apr 09 '19 at 22:23

user1834217

@thelatemail yes, sorry about that. i've modified it. – user1834217 Apr 09 '19 at 22:28
Also this exact issue over at compsci - https://cs.stackexchange.com/questions/85491/algorithm-to-split-an-array-into-minimal-number-of-subarrays-where-sum-of-their – thelatemail Apr 09 '19 at 22:45
And more useful stuff -https://stackoverflow.com/questions/10467579/solving-task-scheduling-or-bin-packing-optimizations-in-r – thelatemail Apr 09 '19 at 22:57
1

I think two important/salient points to take from the other questions' comments are: "bin packing" and "NP hard". – r2evans Apr 09 '19 at 22:59
Can there be negative values also in your input ? Also sorting won't help, that will mess up the order of elements because you want subarrays. – SomeDude Apr 09 '19 at 23:07
@SomeDude there are no negative values – user1834217 Apr 09 '19 at 23:14
A "subarray" is typically defined as contiguous. Is that the case here? – גלעד ברקן Apr 10 '19 at 00:01
If "subarrays" are not contiguous then that is NP-hard. – Yola Apr 10 '19 at 04:43

Splitting an array into subarrys so that we have minimum number of subarrays with sum of elements < k

0 Answers0