backtrack_stack_knapsack.js

var boxes = [
    {id: "A", weight: 12, value: 4},
    {id: "B", weight: 2, value: 2},
    {id: "C", weight: 1, value: 1},
    {id: "D", weight: 4, value: 10},
    {id: "E", weight: 1, value: 2}
];
var knapsack = Stack(function (config) {
    //decide next or finish
    if (config.availableOptions.length) {
        return config.getBox;
    }
    return config;
}).push(function (config) {
    //fit as many as you can
    config.cram = this;
    while (config.weight + config.current.weight <= config.maxWeight) {
        config.packed.push(config.current);
        config.weight += config.current.weight;
    }
    return config;
}).push(function (config) {
    //find most valuable option
    config.getBox = this;
    var box = config.availableOptions.reduce(function (maxBox, box, i, boxes) {
        var ratio = box.value / box.weight;
        var maxRatio = maxBox.value / maxBox.weight;
        if (ratio > maxRatio) {
            return box;
        }
        return maxBox;
    }, {weight: 1, value: -1});
    config.current = box;
    config.availableOptions.splice(config.availableOptions.indexOf(box), 1);
    return config;    
}).push(function () {
    //stage question
    var args = Array.prototype.slice.call(arguments, 0);
    return {
        allOptions: args,
        availableOptions: args.slice(0),
        current: null,
        packed: [],
        weight: 0,
        maxWeight: 15
    };
});

knapsack.apply(boxes);

knapsack is a favorite problem for constraint satisfaction. http://bit.ly/10rNiLe