Дробный рюкзак с использованием JavaScript

Question

Im пытается преобразовать реализацию моего учителя кода psuedo для жадной реализации классической проблемы с рюкзаком, в которой, учитывая сумку, которая может использоваться старым 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)); 

Та часть, которая Im попасться на это в методе захвата, если вы удалите I из набора , Как вы можете обновить xi, потому что ваш индекс i элемента в S w/самом высоком значении не будет соответствовать xi, если вы удаляете элементы из S.

Answer 1

Поскольку дробный рюкзак является жадным алгоритмом, я предлагаю вам сначала отсортировать предметы по их benefit/weight и взять предметы с начала массива, пока ваш рюкзак не будет заполнен. Таким образом, вам не нужно каждый раз выполнять поиск максимального элемента, и вы не столкнетесь с проблемой, с которой вы сталкиваетесь в данный момент.