Revision of gist:7a583fd94b2a4af5bfb6a2f9e1cf797a

Winston Hoy ревизий этого фрагмента 9 years ago. К ревизии

1 file changed, 1 insertion, 1 deletion

cakeThief.js

			@@ -41,7 +41,7 @@ function maxDuffelBagValue (cakeTypes, capacity) {
41	41		smallestCake = getSmallestCakeType(validCakeTypes);
42	42
43	43		// until we don't have enough weight left, find the most valuable cake
44		-	for (capacityLeft = capacity; capacityLeft >= smallestCake.weight; capacityLeft = bag.getCapacityRemaining()) {
	44	+	for (var capacityLeft = capacity; capacityLeft >= smallestCake.weight; capacityLeft = bag.getCapacityRemaining()) {
45	45		// reduce our cakeTypes to the index of the highest value density that can fit
46	46		let bestCake = validCakeTypes.reduce((prev, next) => {
47	47		// make sure this next cake will fit

Winston Hoy ревизий этого фрагмента 9 years ago. К ревизии

1 file changed, 1 insertion, 5 deletions

cakeThief.js

			@@ -35,14 +35,13 @@ let cakeTypes = [
35	35
36	36		function maxDuffelBagValue (cakeTypes, capacity) {
37	37		let bag = new Bag(capacity),
38		-	capacityLeft = capacity,
39	38		// clean our cake types to cover out of bounds values
40	39		validCakeTypes = cleanCakeTypes(cakeTypes),
41	40		// figure out what the smallest cake is
42	41		smallestCake = getSmallestCakeType(validCakeTypes);
43	42
44	43		// until we don't have enough weight left, find the most valuable cake
45		-	while (capacityLeft >= smallestCake.weight) {
	44	+	for (capacityLeft = capacity; capacityLeft >= smallestCake.weight; capacityLeft = bag.getCapacityRemaining()) {
46	45		// reduce our cakeTypes to the index of the highest value density that can fit
47	46		let bestCake = validCakeTypes.reduce((prev, next) => {
48	47		// make sure this next cake will fit
			@@ -56,9 +55,6 @@ function maxDuffelBagValue (cakeTypes, capacity) {
56	55
57	56		// add the cake to our bag (adding to its weight and value)
58	57		bag.addCake(bestCake);
59		-
60		-	// re-calculate our remaining cake capacity
61		-	capacityLeft = bag.getCapacityRemaining();
62	58		}
63	59
64	60		return bag.getValue();

Winston Hoy ревизий этого фрагмента 9 years ago. К ревизии

1 file changed, 84 insertions

cakeThief.js(файл создан)

		@@ -0,0 +1,84 @@
1	+	class Bag {
2	+	constructor (capacity) {
3	+	this.capacity = capacity;
4	+	this.cakes = [];
5	+	this.weight = 0;
6	+	this.value = 0;
7	+	}
8	+
9	+	addCake (cake) {
10	+	this.cakes.push(cake);
11	+	this.value += cake.value;
12	+	this.weight += cake.weight;
13	+	}
14	+
15	+	getCapacityRemaining () {
16	+	return this.capacity - this.getWeight();
17	+	}
18	+
19	+	getValue () {
20	+	return this.value;
21	+	}
22	+
23	+	getWeight () {
24	+	return this.weight;
25	+	}
26	+	}
27	+
28	+	let cakeTypes = [
29	+	{weight: 7, value: 160},
30	+	{weight: 3, value: 90},
31	+	{weight: 1, value: 15}
32	+	];
33	+
34	+	// maxDuffelBagValue(cakeTypes, 20);
35	+
36	+	function maxDuffelBagValue (cakeTypes, capacity) {
37	+	let bag = new Bag(capacity),
38	+	capacityLeft = capacity,
39	+	// clean our cake types to cover out of bounds values
40	+	validCakeTypes = cleanCakeTypes(cakeTypes),
41	+	// figure out what the smallest cake is
42	+	smallestCake = getSmallestCakeType(validCakeTypes);
43	+
44	+	// until we don't have enough weight left, find the most valuable cake
45	+	while (capacityLeft >= smallestCake.weight) {
46	+	// reduce our cakeTypes to the index of the highest value density that can fit
47	+	let bestCake = validCakeTypes.reduce((prev, next) => {
48	+	// make sure this next cake will fit
49	+	if (next.weight <= capacityLeft) {
50	+	// decide which is higher value-weight ratio
51	+	return prev.value / prev.weight > next.value / next.weight ? prev : next;
52	+	}
53	+	// this next cake doesn't fit, keep the previous
54	+	else return prev;
55	+	}, {value: 0, weight: 1});
56	+
57	+	// add the cake to our bag (adding to its weight and value)
58	+	bag.addCake(bestCake);
59	+
60	+	// re-calculate our remaining cake capacity
61	+	capacityLeft = bag.getCapacityRemaining();
62	+	}
63	+
64	+	return bag.getValue();
65	+	}
66	+
67	+	/**
68	+	* reduce our cakeType collection down to one with the lowest weight
69	+	* @param {array} cakeTypes - collection of cakeType object {weight, value}
70	+	* @return {object} cakeType
71	+	*/
72	+	function getSmallestCakeType (cakeTypes) {
73	+	return cakeTypes.reduce((prev, next) => prev.weight < next.weight ? prev : next);
74	+	}
75	+
76	+	/**
77	+	* cleanCakeTypes - filters out invalid cakeTypes
78	+	* @param {array} cakeTypes - collection of cakeType object {weight, value}
79	+	* @return {array} filtered collection of cakeType objects
80	+	*/
81	+	function cleanCakeTypes (cakeTypes) {
82	+	// filter out any cake types with weight or value of 0, that's unreal!
83	+	return cakeTypes.filter((type) => type.weight > 0 && type.value > 0);
84	+	}

Новее Позже