使用 JavaScript 的小数背包

Question

我正在尝试将我老师的伪代码实现转换为经典背包问题的贪婪实现，其中，给定一个可以说 max_weight 的包。选择您想要的物品和背包中物品的重量，以便您获得最大利益。
给出的伪代码

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

我在做什么

// 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));

如果您从集合中删除 i，我遇到的问题是 grab 方法。你怎么能更新 xi 因为如果你从 S 中删除元素，你在 S 中 w/ 最高值的项目的索引 i 不会与 xi 对应。

Answer 1

由于小数背包是一种贪心算法，我建议您首先按 benefit/weight 对项目进行排序，然后从数组的开头取出项目，直到您的背包已满。这样您就不必每次都搜索最大项，也不会遇到您现在遇到的问题。

使用 JavaScript 的小数背包

Fractional knapsack using JavaScript

javascript

algorithm

greedy