1-d optimization with preferential results

1d_optimization.js

// helpers
///////////////////////////////////

function bench(fn) {
    var t0 = new Date().getTime(),
        res = fn();
    console.log("Time: ", new Date().getTime() - t0);
    return res;
}

function sum(ary) {
    var s = 0, i;
    for (i = 0; i < ary.length; ++i) s += ary[i];
    return s;
}

function series(n, min, max) {
    var ss = [];
    for (var i = 0; i < n; ++i) {
        ss.push(parseInt(Math.random() * (max - min)) + min);
    }
    return ss;
}

// 1-d optimization methods
////////////////////////////////////

// the number of calls will be = 2^n-1
function optimize(ss, i, n, r) {
    if (i < n && r.v > 0) {
        var k = optimize(ss, i+1, n, r),
            l = optimize(ss, i+1, n, {
                v: r.v-ss[i],
                oo: r.oo.concat(ss[i])
            });
        r = (l.v >= 0 && l.v <= k.v ? l : k);
    }
    return r;
}

// returns the optimal subset of ss
// to fit supplied volume v without any
// other restrictions
function optimizeAll(ss, v) {
    return bench(function() {
        return optimize(ss, 0, ss.length, {
            v: v, oo: []
        }).oo;
    });
}

// this optimization method guarantees
// to contain the largest possible value
function optimizeRest(ss, v) {
    var ss_ = ss.slice().sort(function(a,b){return a-b}),
        mx = ss_.splice(-1, 1);
    return bench(function() {
        return optimize(ss_, 0, ss_.length, {
            v: v - mx, oo: []
        }).oo.concat(mx);
    });
}

// examples
/////////////////////////////////////////

console.clear();

var _ss = series(10, 400, 800), _ra, _rr;
console.log(_ss);

_ra = optimizeAll(_ss, 1920);
console.log('all: ', _ra, sum(_ra));

_rr = optimizeRest(_ss, 1920);
console.log('rest:', _rr, sum(_rr));