InterviewCake - The Cake Theif
// FROM: https://www.interviewcake.com/question/cake-thief
function max_duffel_bag_value(cake_tuples, capacity){
var value = 0,
current_weight = 0;
cake_tuples = cake_tuples.map(function(cake_tuple){
var weight = cake_tuple[0],
value = cake_tuple[1],
ratio = value / weight;
return [weight, value, ratio];
});
cake_tuples.sort(function(a, b){
return b[2] - a[2];
});
cake_tuples.forEach(function(cake_tuple){
var i = 0;
while(i < cake_tuple[0] && current_weight < capacity ) {
value += cake_tuple[1];
current_weight++;
i++;
}
if (current_weight === capacity){
return false;
}
});
return value;
}
var cake_tuples = [[0, 0], [3, 90], [2, 15]];
var capacity = 100;
max_duffel_bag_value(cake_tuples, capacity);