/**
* Created by Kudelin Oleg on 02.12.13.
* Задача нахождения предельного числа предметов, способных уместиться в рюкзаке
* с максимальной суммарной стоимостью.
* Используется метод поиска в глубину с обратным восстановлением пути
*/
var TASK_RUCKSACK = TASK_RUCKSACK || {};
/**
* Конструктор рюкзака
* @param maximumRucksackWeight максимальная вместимость
* @constructor
*/
TASK_RUCKSACK.Rucksack = function(maximumRucksackWeight) {
this.maximumRucksackWeight = maximumRucksackWeight;
this.arrayOfThingsForPutInRucksack = undefined;
this.currentMaxPrice = 0;
this.currentArray = [];
};
TASK_RUCKSACK.Rucksack.prototype = {
//=============public==================
/**
* Установка максимальной вместимости
* @param maxWeight
*/
set maxWeight(maxWeight) {
this.maximumRucksackWeight = maxWeight;
},
/**
* Возвращает набор вещей с максимальной суммарной стоимостью
* @param arrayOfThings Массив объектов вида {cost: number, weight : number}
* @returns {{totalPrice: number, thingArray: Array}}
*/
getThingWithMaximumCost : function(arrayOfThings) {
this.arrayOfThings = arrayOfThings;
if (this.arrayOfThings == undefined) {
console.warn("Отсутствует перечень вещей");
return;
}
if (this.maxWeight == undefined) {
console.warn("Не задан максимальный вес");
return;
}
this.checkNextThing(0,0,0,0);
return {
totalPrice : this.currentMaxPrice,
thingArray : this.currentArray.map(
(function(index) {
return (this.arrayOfThings)[index];
}).bind(this)
)
}
},
get maxWeight() {
return this.maximumRucksackWeight;
},
//============private==================
set arrayOfThings(arrayOfThings) {
if (Array.isArray(arrayOfThings)) {
this.arrayOfThingsForPutInRucksack = arrayOfThings;
} else {
console.error("Не допустимый формат. Должен быть массив");
}
},
get arrayOfThings() {
return this.arrayOfThingsForPutInRucksack;
},
isOut : function(index, weight) {
return ((index > this.arrayOfThings.length - 1)||(weight > this.maxWeight))
},
resetMaxArray : function() {
this.currentArray.length = 0;
},
isMaxCost : function(cost) {
return (this.currentMaxPrice < cost);
},
setMaxCost : function(cost) {
this.currentMaxPrice = cost;
this.resetMaxArray();
},
// собственно сама рекурсивная функция поиска
checkNextThing : function(currentWeight, indexThing, currentCost, currentCostLast) {
if (this.isOut(indexThing, currentWeight)) {
var temCost = (currentWeight > this.maxWeight) ? currentCostLast : currentCost;
if (this.isMaxCost(temCost)) {
this.setMaxCost(temCost);
return true;
}
return false;
}
var cost1 = this.checkNextThing(currentWeight, indexThing + 1, currentCost, currentCost);
var cost2 = this.checkNextThing(currentWeight + this.arrayOfThings[indexThing].weight, indexThing + 1, currentCost + this.arrayOfThings[indexThing].cost, currentCost);
if (cost2) {
this.currentArray.push(indexThing);
}
return cost1||cost2;
}
};
(function() {
var rucksack = new TASK_RUCKSACK.Rucksack(7);
var thing = rucksack.getThingWithMaximumCost([
{cost: 10, weight : 2},
{cost: 10, weight : 2},
{cost: 3, weight : 1},
{cost: 2, weight : 1},
{cost: 10, weight : 1},
{cost: 20, weight : 1},
{cost: 2, weight : 1},
{cost: 2, weight : 1},
{cost: 2, weight : 1},
{cost: 12, weight : 5},
{cost: 12, weight : 5},
{cost: 12, weight : 5},
{cost: 13, weight : 3}]
);
document.write("Total price " + thing.totalPrice + "<br>");
thing.thingArray.forEach(
function(value) {
document.write("Cost " + value.cost + " weight " + value.weight + "<br>");
}
);
})();
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.