knapsack_bruteForce.js

Home   »   knapsack_bruteForce.js

var items = {
    stereo: {weight:5, worth:50},
    guitar: {weight:2, worth:35},
    piano: {weight:10, worth:85},
    mp3: {weight:1, worth:21},
    cdPlayer: {weight:1, worth:15},
    picture: {weight:2, worth:25},
    laptop: {weight:3, worth:100},
    tv: {weight:7, worth:97},
    coffeMachine: {weight:4, worth:47},
    vacuum: {weight:7, worth:61},
    statue: {weight:12, worth:250},
    doll: {weight:1, worth:5}
}

function knapSack(sacCapacity, items){ 
    if (sacCapacity < 0 ) return false
    if (Object.keys(items).length === 0) return true; 
    
    let currentBest = {items:[], totalWorth:0};                     // returns the best option so far (at each level) 
    
    for(let item in items){
        let spaceLeft = sacCapacity - items[item].weight;
        let itemsLeft = {...items}
            delete itemsLeft[item];
        
        let prevBest = knapSack(spaceLeft, itemsLeft);
        if (typeof prevBest === 'object'){
            prevBest.items.push(item);
            prevBest.totalWorth += items[item].worth;
            
            if( prevBest.totalWorth > currentBest.totalWorth){
                Object.assign(currentBest, prevBest);
            }
        } else if (prevBest) {
            currentBest.items.push(item);
            currentBest.totalWorth = items[item].worth;
        } 
    }
    
    return currentBest;
}


console.log( knapSack(11, items) );
    // -> { 
    //      items: [ 'coffeMachine', 'laptop', 'cdPlayer', 'mp3', 'guitar' ],
    //      totalWorth: 218
    //    }
    
console.log( knapSack(8, items) );
    // -> { items: [ 'laptop', 'picture', 'mp3', 'guitar' ], totalWorth: 181 }

console.log( knapSack(21, items) );
    // -> {
    //      items: [ 'statue', 'laptop', 'picture', 'cdPlayer', 'mp3', 'guitar' ],
    //      totalWorth: 446
    //    }
    
console.log( knapSack(17, items) );
   // -> { items: [ 'statue', 'laptop', 'cdPlayer', 'mp3' ], totalWorth: 386 }

Leave a Reply

Your email address will not be published. Required fields are marked *