Javascript Knapsack Algorithm - find by lowest value

Question

I have found an implementation of Knapsack problem. As you probably all know this algorithm is designed to find solution with the highest value of items that fits in backpack. I want to make it finds solution with the lowest values.

Here is the code:

var data= [
    {name: 'map',                    weight:  9, value:150, pieces:1},
    {name: 'compass',                weight: 13, value: 35, pieces:1},
    {name: 'water',                  weight:153, value:200, pieces:2},
    {name: 'sandwich',               weight: 50, value: 60, pieces:2},
    {name: 'glucose',                weight: 15, value: 60, pieces:2},
    {name: 'tin',                    weight: 68, value: 45, pieces:3},
    {name: 'banana',                 weight: 27, value: 60, pieces:3},
    {name: 'apple',                  weight: 39, value: 40, pieces:3},
    {name: 'cheese',                 weight: 23, value: 30, pieces:1},
    {name: 'beer',                   weight: 52, value: 10, pieces:3},
    {name: 'suntan, cream',          weight: 11, value: 70, pieces:1},
    {name: 'camera',                 weight: 32, value: 30, pieces:1},
    {name: 'T-shirt',                weight: 24, value: 15, pieces:2},
    {name: 'trousers',               weight: 48, value: 10, pieces:2},
    {name: 'umbrella',               weight: 73, value: 40, pieces:1},
    {name: 'waterproof, trousers',   weight: 42, value: 70, pieces:1},
    {name: 'waterproof, overclothes',weight: 43, value: 75, pieces:1},
    {name: 'note-case',              weight: 22, value: 80, pieces:1},
    {name: 'sunglasses',             weight:  7, value: 20, pieces:1},
    {name: 'towel',                  weight: 18, value: 12, pieces:2},
    {name: 'socks',                  weight:  4, value: 50, pieces:1},
    {name: 'book',                   weight: 30, value: 10, pieces:2}
];

function findBestPack() {
    var m= [[0]]; // maximum pack value found so far
    var b= [[0]]; // best combination found so far
    var opts= [0]; // item index for 0 of item 0
    var P= [1]; // item encoding for 0 of item 0
    var choose= 0;
    for (var j= 0; j<data.length; j++) {
        opts[j+1]= opts[j]+data[j].pieces; // item index for 0 of item j+1
        P[j+1]= P[j]*(1+data[j].pieces); // item encoding for 0 of item j+1
    }
    for (var j= 0; j<opts[data.length]; j++) {
        m[0][j+1]= b[0][j+1]= 0; // best values and combos for empty pack: nothing
    }
    for (var w=1; w<=400; w++) {
        m[w]= [0];
        b[w]= [0];
        for (var j=0; j<data.length; j++) {
            var N= data[j].pieces; // how many of these can we have?
            var base= opts[j]; // what is the item index for 0 of these?
            for (var n= 1; n<=N; n++) {
                var W= n*data[j].weight; // how much do these items weigh?
                var s= w>=W ?1 :0; // can we carry this many?
                var v= s*n*data[j].value; // how much are they worth?
                var I= base+n; // what is the item number for this many?
                var wN= w-s*W; // how much other stuff can we be carrying?
                var C= n*P[j] + b[wN][base]; // encoded combination
                m[w][I]= Math.max(m[w][I-1], v+m[wN][base]); // best value
                choose= b[w][I]= m[w][I]>m[w][I-1] ?C :b[w][I-1];
            }
        }
    }
    var best= [];
    for (var j= data.length-1; j>=0; j--) {
        best[j]= Math.floor(choose/P[j]);
        choose-= best[j]*P[j];
    }

I have tried several things, but it didn't work for me, can you guys help me out?

Algorithm finds items that fits in container that has 400 capacity so it can contain items that has no more than 400 weight. It also try to fits items that have the best value. For example if 1 item has 10 weight and 5 value algorithm will take this item instead of item with 10 weight and 4 value. I want to make it reverse when it comes to value so algorithm will pick the item with 4 value instead of 5.

Answer 1

In general, the solution to the vanilla Knapsack problem for lowest values is trivial: you can simply choose to take nothing. If you're talking about lowest value for a certain weight threshold, then here's a hint: try negating all your values. In this case, the highest value knapsack is the least negative.