Knapsack algorithm in JavaScript - Integer weights and values

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 valu

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

StackExchange Code Review Q#135452, answer score: 4