Вариант рюкзака в JavaScript

Question

Я попытался реализовать это knapsack problem solution algorithm в JavaScript, но решения s_opt, которые я получаю, имеют общий вес больше, чем L_max.

Что я делаю неправильно?

Я подозреваю, что это может быть связано с Closures in recursion.

/* 
GENERAL: 
    Assume we have a knapsack and we want to bring as much stuff as possible. 
    Of each thing we have several variants to choose from. Each of these variants have 
    different value and takes different amount of space. 

DEFINITIONS: 
    L_max = integer, size of the knapsack for the entire problem having N items 
    l = matrix, having the elements l[i-1][j-1] representing the space taken 
      by variant j of item i (-1 since indexing the matrices has index starting on zero, i.e. item i is stored at position i-1) 
    p = matrix, having the elements p[i-1][j-1] representing the value given by 
      by variant j of item i 
    n = total number of items (used in a sub-problem) 
    N = total number of items (used in the full problem, N >= n) 
    s_opt = vector having the optimal combination of variant selections s_i, i.e. s_opt = arg max p_sum 

*/ 
function knapsack(L_max,l,p) { 

    // constructing (initializing) - they are private members 
    var self = this; // in order for private functions to be able read variables 
    this.N = l.length; 
    var DCached = []; // this is only used by a private function so it doesnt need to made public using this.* 
    this.s_opt = []; 
    this.p_mean = null; 
    this.L_max = L_max; 

    // define public optimization function for the entire problem 
    // when this is completed the user can read 
    // s_opt to get the solution and 
    // p_mean to know the quality of the solution 
    this.optimize = function() { 
     self.p_mean = D(self.N,self.L_max)/Math.max(1,self.N); 
    } 

    // define private sub-problem optimization function 
    var D = function(n,r) { 
     if (r<0) 
     return -Infinity; 
     if (n==0) 
     return 0; 
     if(DCached[n-1] != null) { 
     if(DCached[n-1][r-1] != null) { 
      return DCached[n-1][r-1]; 
     } 
     } 
     var p_max = -Infinity; 
     var p_sum; 
     var J = l[n-1].length; 
     for(var j = 0; j < J; j++) { 
     p_sum = p[n-1][j] + D(n-1 , r - l[n-1][j]); 
     if(p_sum>p_max) { 
      p_max = p_sum; 
      self.s_opt[n-1] = j; 
     } 
     } 
     DCached[n-1] = []; 
     DCached[n-1][r-1] = p_max; 
     return p_max; 
    } 
} 

Клиент с помощью этого рюкзака решатель выполняет следующие действия:

var knapsackSolution = new knapsack(5,l,p); 
knapsackSolution.optimize(); 
// now the client can access knapsackSolution.s_opt containing the solution. 

Answer 1

Я нашел решение. При решении подзадачи D(n,r) код в вопросе возвращал оптимизированное значение, но он действительно не управлял массивом s_opt надлежащим образом. В модифицированном решении, вставленном ниже, я исправил это. Вместо того, чтобы возвращать только оптимизированное значение ранца, возвращается массив выбранных вариантов (например, аргумент max). Кэш также модифицирован для управления этими двумя частями решения (как максимальное значение, так и значение arg max).

В приведенном ниже коде также содержится дополнительная функция. Теперь пользователь может также передать значение maxComputingComplexity, контролируя вычислительный размер проблемы каким-то эвристическим способом.

/* 
GENERAL: 
    Assume we have a knapsack and we want to bring as much stuff as possible. 
    Of each thing we have several variants to choose from. Each of these variants have 
    different value and takes different amount of space. 

    The quantity of each variant is one. 

DEFINITIONS: 
    L_max = integer, size of the knapsack, e.g. max number of letters, for the entire problem having N items 
    l = matrix, having the elements l[i-1][j-1] representing the space taken 
      by variant j of item i (-1 since indexing the matrices has index starting on zero, i.e. item i is stored at position i-1) 
    p = matrix, having the elements p[i-1][j-1] representing the value given by 
      by variant j of item i 
    maxComputingComplexity = value limiting the product L_max*self.N*M_max in order to make the optimization 
      complete in limited amount of time. It has a serious implication, since it may cut the list of alternatives 
      so that only the first alternatives are used in the computation, meaning that the input should be well 
      ordered 
    n = total number of items (used in a sub-problem) 
    N = total number of items (used in the full problem, N >= n) 
    M_i = number of variants of item i 
    s_i = which variant is chosen to pack of item i 
    s = vector of elements s_i representing a possible solution 
    r = maximum total space in the knapsack, i.e. sum(l[i][s_i]) <= r 
    p_sum = sum of the values of the selected variants, i.e. sum(p[i][s_i] 
    s_opt = vector having the optimal combination of variant selections s_i, i.e. s_opt = arg max p_sum 

    In order to solve this, let us see p_sum as a function 
    D(n,r) = p_sum (just seeing it as a function of the sub-problem n combined with the maximum total space r) 
RESULT: 
*/ 

function knapsack(L_max,l,p,maxComputingComplexity) { 


    // constructing (initializing) - they are private members 
    var self = this; // in order for private functions to be able read variables 
    this.N = l.length; 
    var DCached = []; // this is only used by a private function so it doesnt need to made public using this.* 
    //this.s_opt = []; 
    //this.p_mean = null; 
    this.L_max = L_max; 
    this.maxComputingComplexity = maxComputingComplexity; 
    //console.log("knapsack: Creating knapsack. N=" + N + ". L_max=" + L_max + "."); 

    // object to store the solution (both big problem and sub-problems) 
    function result(p_max,s_opt) { 
     this.p_max = p_max; //max value 
     this.s_opt = s_opt; //arg max value 
    } 

    // define public optimization function for the entire problem 
    // when this is completed the user can read 
    // s_opt to get the solution and 
    // p_mean to know the quality of the solution 
    // computing complexity O(L_max*self.N*M_max), 
    // think O=L_max*N*M_max => M_max=O/L_max/N => 3=x/140/20 => x=3*140*20 => x=8400 
    this.optimize = function() { 
     var M_max = Math.max(maxComputingComplexity/(L_max*self.N),2); //totally useless if not at least two 
     console.log("optimize: Setting M_max =" + M_max); 
     return D(self.N,self.L_max,M_max); 
     //self.p_mean = mainResult.D/Math.max(1,self.N); 
     // console.log... 
    } 

    // Define private sub-problem optimization function. 
    // The function reads to "global" variables, p and l 
    // and as arguments it takes 
    //  n delimiting the which sub-set of items to be able to include (from p and l) 
    //  r setting the max space that this sub-set of items may take 
    // Based on these arguments the function optimizes D 
    // and returns 
    //  D the max value that can be obtained by combining the things 
    //  s_opt the selection (array of length n) of things optimizing D 
    var D = function(n,r,M_max) { 
     // Start by checking whether the value is already cached... 
     if(DCached[n-1] != null) { 
     if(DCached[n-1][r-1] != null) { 
      //console.log("knapsack.D: n=" + n + " r=" + r + " returning from cache."); 
      return DCached[n-1][r-1]; 
     } 

     } 
     var D_result = new result(-Infinity, []); // here we will manage the result 
     //D_result.s_opt[n-1] = 0; // just put something there to start with 
     if (r<0) { 
      //D_result.p_max = -Infinity; 
      return D_result; 
     } 
     if (n==0) { 
      D_result.p_max = 0; 
      return D_result; 
     } 
     var p_sum; 
     //self.s_opt[n] = 0; not needed 
     var J = Math.min(l[n-1].length,M_max); 
     var D_minusOneResult; //storing the result when optimizing all previous items given a max length 
     for(var j = 0; j < J; j++) { 
      D_minusOneResult = D(n-1 , r - l[n-1][j] , M_max) 
      p_sum = p[n-1][j] + D_minusOneResult.p_max; 
      if(p_sum > D_result.p_max) { 
       D_result.p_max = p_sum; 
       D_result.s_opt = D_minusOneResult.s_opt; 
       D_result.s_opt[n-1] = j; 
      } 

     } 
     DCached[n-1] = []; 
     DCached[n-1][r-1] = D_result; 
     //console.log("knapsack.D: n=" + n + " r=" + r + " p_max= "+ p_max); 
     return D_result; 
    } 
}