Solving The Knapsack Problem

knapsackSolved.js

// inspired by Academind's "JavaScript Algorithms Crash Course" 
// see https://www.youtube.com/watch?v=JgWm6sQwS_I for more like this

// Imagine you have a list of items, and each item has a value and a weight associated with it.
items = [
	{ id: "b", val: 6, w: 8 },
	{ id: "a", val: 10, w: 3 },
	{ id: "c", val: 3, w: 3 },
];

// Original example was pre-sorted by value decreasing, but I mixed up the order above to make it more realistic.
items.sort( function(b,a){
    if (a.val > b.val) return 1;
    if (a.val < b.val) return -1;	
	
    // if two items have same value, we can rank by weight (lightest item first)!
    if (a.val == b.val) {
        if (a.w > b.w) return 1;
        if (a.w < b.w) return -1;
    }
    
    return 0; // if equal in value and wt, leave them be
});

// How can we get the highest total value of items in the bag, without exceeding its weight capacity?

// first, we need a bag
function Bag(wl){
    let obj = {};

    obj.wtLimit = wl;
    obj.contents = [];

    // then we figure out how to stuff bag without exceeding its limit
    obj.stuffBag = function(items){
        items.forEach( function(item){
            if (item.w <= obj.wtLimit) { 
                obj.contents.push(item);
                obj.wtLimit -= item.w;
            }
        });
    };

    return obj;
}

// nothing to it, but to do it.
let myBag = new Bag(8);
myBag.stuffBag(items);
console.log( myBag.contents );