Solutions
Solution 1 (Click to Show/Hide)
function knapsackUnbounded(items, maxWeight, maxVolume) {
function getPickTotals(items, pick) {
let totalValue = 0;
let totalWeight = 0;
let totalVolume = 0;
for (let i = 0; i < items.length; i++) {
totalValue += pick[i] * items[i].value;
totalWeight += pick[i] * items[i].weight;
totalVolume += pick[i] * items[i].volume;
}
return [totalValue, totalWeight, totalVolume];
}
function getMaxes(items, maxWeight, maxVolume) {
const maxes = [];
for (let i = 0; i < items.length; i++) {
const maxUnitsInWeight = Math.floor(maxWeight / items[i].weight);
const maxUnitsInVolume = Math.floor(maxVolume / items[i].volume);
const maxUnitsInLimit = Math.min(maxUnitsInWeight, maxUnitsInVolume);
maxes.push(maxUnitsInLimit);
}
return maxes;
}
function isInLimit(value, limit) {
return value <= limit;
}
function getCombinations(maxValues, curPicks, combinations) {
if (maxValues.length === 0) {
combinations.push(curPicks);
}
const curMax = maxValues[0];
const leftMaxValues = maxValues.slice(1);
for (let i = 0; i <= curMax; i++) {
getCombinations(leftMaxValues, curPicks.concat(i), combinations);
}
return combinations;
}
let bestValue = 0;
let bestPick = [];
const maxes = getMaxes(items, maxWeight, maxVolume);
const combinations = getCombinations(maxes, [], []);
for (let i = 0; i < combinations.length; i++) {
const curPick = combinations[i];
const [curValue, curWeight, curVolume] = getPickTotals(items, curPick);
if (!isInLimit(curWeight, maxWeight) || !isInLimit(curVolume, maxVolume)) {
continue;
}
if (curValue > bestValue) {
bestValue = curValue;
bestPick = [curPick];
} else if (curValue === bestValue) {
bestPick.push(curPick);
}
}
return bestValue;
}