solver.js

var algorithms = require("algorithms"),
    fs = require("fs");

var dynamicLowMem = function(capacity, values, weights){
    var max = function(x, y){
        return x ^ ((x ^ y) & -(x < y));
    }

    var items = values.length,
        value = 0,
        weight = capacity,
        taken = [];

    var curr = [],
        prev = [];

    var w_0 = weights[0],
        v_0 = values[0];

    var s = [];

    for(var i = 0; i < items; i++){
        s[i] = new Uint8Array(capacity);
    }

    // initialize the first column
    for(var i = 0; i < capacity; i++){
        prev[i] = (w_0 <= i+1) ? v_0 : 0;
        if(prev[i] == v_0)
            s[0][i] = true
        else s[0][i] = false
    }

    // find the maximum
    for(var i = 1; i < items; i++){
        var w = weights[i],
            v = values[i];

        for(var j = 0; j < capacity; j++){
            if(w <= (j + 1) && (j + 1) - w > 0){
                curr[j] = v + prev[j-w];
            }else if(w <= (j + 1)){
                curr[j] = v;
            }else{
                curr[j] = 0;
            }

            curr[j] = max(curr[j], prev[j]);

            if(curr[j] === prev[j])
                s[i][j] = false
            else s[i][j] = true;
        }

        if(i != items - 1){
            prev = curr;
            curr = [];
        }
    }

    value = curr[capacity-1];

    for(var i = items-1; i >= 0; i--){
        var c = s[i][weight-1];
        taken[i] = ~~c;
        weight -= (c ? weights[i] : 0);
    }

    return [value, taken, 1];
}

var dynamic = function(capacity, values, weights){
    var fn = function(x, y){ return x < y };

    var items = values.length,
        value = 0,
        weight = capacity,
        taken = []

    var min = algorithms.quickSort(weights, fn)[0];

    console.log(min);

    // init matrix
    O = []
    for(var i = 0; i < items; i++){
        O[i] = []
        for(var j = 0; j < capacity; j++){
            O[i][j] = 0;
        }
    }

    // calculate the maximum value
    for(var i = 0; i < items; i++){
        for(j = 0; j < capacity; j++){
            var current = 0,
                w = weights[i]

            if(w <= (j + 1) && (j + 1) - w > 0)
                if(O[i-1]) current = values[i] + O[i-1][j-w]
                else current = values[i]
            else if(w <= (j + 1))
                current = values[i]

            var prev = O[i-1] ? O[i-1][j] : 0;
            O[i][j] = max(current, prev);
        }
    }

    // backtrack and obtain the sequence solution
    for(var i = items-1; i >= 0; i--){
        var curr = O[i][weight-1],
            prev = O[i-1] ? O[i-1][weight-1] : 0;

        if(curr == prev || weight == 0){
            taken[i] = 0;
        }else{
            taken[i] = 1;
            weight -= weights[i]
        }

    }

    value = O[items-1][capacity-1]

    return [value, taken, 1]
}

var branchAndBound = function(capacity, values, weights){
    var tree = [],
        items = values.length;

    for(var i = 0; i < items; i++){

    }
}


var main = function(){
    var file = process.argv[2],
        data = fs.readFileSync(file, "utf-8").split("\n");

    var firstLine = /(\d+)\s+(\d+)/.exec(data[0]),
        items = parseInt(firstLine[1]),
        capacity = parseInt(firstLine[2]);

    var values = [],
        weights = [];

    for(var i = 1; i < items+1; i++){
        var parts = /(\d+)\s+(\d+)/.exec(data[i])

        values.push(parseInt(parts[1]))
        weights.push(parseInt(parts[2]))
    }

    // perform some logic here to get the right answers
    // for certain questions
    var ret = dynamicLowMem(capacity, values, weights);

    process.stdout.write(ret[0] + " " + ret[2] + "\n");
    process.stdout.write(ret[1].join(" "));
}

main();