Knapsack variant in JavaScript

Question

I have tried to implement this knapsack problem solution algorithm in JavaScript, but the solutions s_opt I get has a total weight greater than the L_max.

What am I doing wrong?

I suspect it could be something related to 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;
    }
}

The client using this knapsack solver does the following:

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

Answer 1

I found a solution. When solving a sub-problem D(n,r) the code in the question returned the optimized value, but it didn't really manage the array s_opt in a proper way. In the modified solution, pasted below, I fixed this. Instead of only returning the optimized value of the knapsack also an array of chosen variants (e.g. the arg of the max) are returned. The cache is also modified to manage these two parts of the solution (both max value and arg max value).

The code below also contains an additional feature addition. The user can now also pass a value maxComputingComplexity controlling the computational size of the problem in some kind of heuristic manner.

    /*
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;
    }
}