Last active
November 9, 2021 10:13
-
-
Save Richienb/3ba40120ba96adbb1520cac2536553d5 to your computer and use it in GitHub Desktop.
Complete greedy algorithm https://en.wikipedia.org/wiki/Greedy_number_partitioning#Exact_algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function split(array, groups = 2) { | |
array = array.sort((a, b) => b - a); | |
const parts = Array.from({length: groups}, () => []); | |
const partLengths = Array.from({length: groups}, () => 0); | |
for (const item of array) { | |
const partIndex = partLengths.indexOf(Math.min(...partLengths)); | |
parts[partIndex].push(item); | |
partLengths[partIndex] += item; | |
} | |
return parts; | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function split(array) { | |
array = array.sort((a, b) => b - a); | |
const a = []; | |
let aSum = 0; | |
const b = []; | |
let bSum = 0; | |
for (const item of array) { | |
if (aSum < bSum) { | |
a.push(item); | |
aSum += item; | |
} else { | |
b.push(item); | |
bSum += item; | |
} | |
} | |
return [a, b]; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment