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?
