Created
October 8, 2016 01:56
-
-
Save kellyrmilligan/68eba6610270779f69f98668bdaf4ab4 to your computer and use it in GitHub Desktop.
algo examples
This file contains 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
const readline = require('readline'); | |
process.stdin.setEncoding('utf8'); | |
let n = null | |
let w = null | |
let firstParamsSet = false | |
let values = [] | |
const rl = readline.createInterface({ | |
input: process.stdin, | |
terminal: false | |
}); | |
rl.on('line', readLine) | |
function maxLoot(capacity, values) { | |
let maxValue = 0.0000 | |
let sortedLoot = values.sort((valueA, valueB) => { | |
return (valueB.v/valueB.w) - (valueA.v/valueA.w) | |
}) | |
sortedLoot.every((loot) => { | |
if (loot.w <= capacity) { | |
//take all of it | |
maxValue += loot.v | |
capacity = capacity - loot.w | |
} else { | |
//take a fraction | |
maxValue += (capacity/loot.w) * loot.v | |
capacity = capacity - ((capacity/loot.w) * loot.w) | |
} | |
return !capacity <= 0 | |
}) | |
return maxValue.toFixed(4) | |
} | |
function readLine(line) { | |
if (line !== "\n") { | |
line.trim() | |
const parts = line.toString().split(" ") | |
if (!firstParamsSet) { | |
n = parts[0] * 1 | |
w = parts[1] * 1 | |
firstParamsSet = true | |
return | |
} | |
//keep on getting values until it matches n | |
values.push({ v: parts[0] * 1, w: parts[1] * 1 }) | |
if (values.length === n) { | |
console.log(maxLoot(w, values)) | |
rl.close() | |
process.exit() | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment