Knapsack algorithm in JavaScript - Integer weights and values

Question

My version of Knapsack works only when the weights or values of items are whole numbers.

Restrictions

• You are given an array of objects each of which contains a weight and value.
• You are also given a bag which has a maximum capacity.
• Both the values and weights for every item are integers. This example will not cover cases where the weights/values contain decimals
• The maximum capacity will also be a whole number, again no decimals.

Here is my code with commentary

var result = document.getElementById("result"); function knapsack(items, capacity) { var totalWeight = 0; var totalValue = 0; 

Here I initialized the total weight and value of our bag, which is empty at first, so both are zero.

 var sorted = items.sort(function(a,b) { return (b.value / b.weight) - (a.value / a.weight); }); 

To get the most bang for the buck, I'm taking a greedy algorithm and first choosing the item with the highest value to weight ratio. I have to sort the array based on the item's value per cost. I will then set the index to zero, to start at the best value.

 var index = 0; while (totalWeight < capacity) { var ratio = sorted[index].value / sorted[index].weight; totalValue += ratio; totalWeight++; if (totalWeight === sorted[index].weight) { index++; } } 

The loop is run until the weight is equal to the capacity. For every item, I will get the value per 1 unit of weight. This will be added to the value of the bag, whereas the weight of the bag will increase by one unit.

If the weight of the bag equals the weight of the item, I will move on to the next item and continue the while loop.

 return totalValue.toFixed(2); } var array = [ {"value": 15, "weight": 10}, {"value": 24, "weight": 15}, {"value": 25, "weight": 18} ]; result.innerHTML = knapsack(array, 20); 

This will not work if the item weights or values have decimals, but that's beyond the scope of this problem. This problem assumes that all are whole numbers.

What would the complexity be of this algorithm? Also, which type of knapsack does my algorithm solve?

Answer 1

I don't think your algorithm actually works.

First...

while (totalWeight < capacity) { 

...is not the proper criteria for determining when loading into the knapsack should be completed. What if the knapsack capacity is 10 and you got passed 4 objects each having weight of 3? The most you could ever get in the knapsack is a weight of 9. With your condition as is, you would get an infinite loop.

Second...

 totalValue += ratio; 

...makes no sense. Why are you adding the value/weight ratio to the total value summation?

Third...

 totalWeight++; 

...also makes no sense. Why are you incrementing the total weight?

Probably something like the following is what you would need

function knapsack(items, capacity) { let totalValue = 0; let totalWeight = 0; let remainingItems = items.sort( (a, b) => { return (b.value / b.weight) - (a.value / a.weight); }); while (remainingItems.length > 0) { const remainingCapacity = capacity - totalWeight; remainingItems = remainingItems.filter( (item) => { return (item.weight <= remainingCapacity); }); if (remainingItems.length === 0) continue; const addedItem = remainingItems.shift(); totalValue = totalValue + addedItem.value; totalWeight = totalWeight + addedItem.weight; } return totalValue.toFixed(2); } 

Note that this would work even with floats, however this does not validate input data against weight = 0 items which would cause error. In production code, it might be needed to validate the item being passed against this (and possibly other things like negative values/weight, negative/zero capacity, etc.)

Answer 2

This is not the classical backpack problem. Below, the problem that you want to try to solve.

You have a backpack, and in front of you there are n bags. Let us say three bags with different materials. E.g.: One for gold, one for silver, and another for copper. Each bag contains pieces of 1 unit (let's say 1g) for its material. You want to fill up the backpack in the way that you have the maximum value for the capacity of your backpack.

However, even with this specific proposition, there is a problem with the fragment below:

if (totalWeight === sorted[index].weight) { index++; } 

For the first item, it would make sense, but then ... it does not. Maybe you should use another variable for partialWeight of each material. Ex:

totalWeight++; partialWeight++; if (partialWeight === sorted[index].weight) { index++; partialWeight=0; }