Fractional knapsack using JavaScript

Question

Im trying to convert my teacher's implementation of psuedo code for a greedy implementation of the classic knapsack problem in which, given a bag that can old said max_weight. Choose the items you want and the weight of the items for your knapsack so that you maximize your benefit.
The Psuedo Code Given

initialize(S)
    if S is empty then return
    i <-- any element of S
    Xi <-- 0
    Vi <-- bi/wi
    initialize (S-{i})

grab(S)
   if w >= W or S is empty then return 
   i <-- item in S w/ highest value 
   ... update Xi, update w....
   grab(S-{i})

What I Got Up To

// Test Items, [weight, benefit]
var test_input = [
    [4, 12],
    [8, 32],
    [2, 40],
    [6, 30],
    [1, 50]
];

// Output, [weight of item at index];
var test_output = [0, 1, 2, 6, 1];

var fractionalKnapsack = function(knapsack, max_weight) {
    var amt_to_take = [];
    var value = [];
    var curr_weight = 0;

    (function initialize(i) {
        if (i >= knapsack.length) return;

        amt_to_take[i] = 0;
        var weight = knapsack[i][0];
        var benefit = knapsack[i][1];
        value[i] = benefit / weight;
        initialize(++i);
    })(0);

    (function grab(knapsack, value) {
        if (curr_weight >= max_weight || knapsack.length < 1) return;

        var max_value_i = findMax(value);
        console.log(max_value_i);
        var weight_available = max_weight - curr_weight;

        var item_weight;
        if (knapsack[max_value_i][0] <= weight_available) {
            weight = knapsack[max_value_i][0];
        } else {
            weight = weight_available;
        }
        curr_weight += weight;

        knapsack.splice(max_value_i, 1); // remove ith element from knapsack
        value.splice(max_value_i, 1); // remove ith element from value
        grab(knapsack, value);
    })(knapsack.slice(), value.slice());

    function findMax(arr) {
        var max = Number.MAX_VALUE * -1;
        var max_i = -1;

        for (var i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
                max_i = i;
            }
        }

        return max_i;
    }

    return amt_to_take;
}

console.log(fractionalKnapsack(test_input));

The part that Im getting caught up on is in the grab method, if you remove i from the set. How can you update xi because your index i of the item in S w/ highest value is not going to correspond with xi if you are removing elements from S.

Answer 1

As fractional knapsack is a greedy algorithm I suggest you first sort the items by their benefit/weight and take items from the start of the array until your knapsack is full. This way you don't have to search for the max item every time and you won't face the problem you are having at the moment.