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

Я нашел решение. При решении подзадачи D(n,r) код в вопросе вернул оптимизированное значение, но на самом деле он не управлял массивом s_opt должным образом. В модифицированном решении, вставленном ниже, я исправил это. Вместо того, чтобы возвращать только оптимизированное значение рюкзака, также возвращается массив выбранных вариантов (например, аргумент 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;
    }
}