steveosoule
11/12/2014 - 6:21 PM

InterviewCake - The Cake Theif

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);