dp knapsack

dp-knapskack.js

items=[{v: 5, w: 10}, {v: 1, w: 1}, {v: 3, w: 4}]

knp = (items, maxWeight)=>{
    const dp = [];

    for(let i=0; i<=items.length; i++) {
        for(let w=0; w<=maxWeight; w++) {
            if(!dp[i]) dp[i] = [];
            dp[i][w] = 0;
        }
    }

    for(let i=1; i<=items.length; i++) {
        for(let w=1; w<=maxWeight; w++) {
            let cur = items[i-1];
            let notIncludingCur = dp[i-1][w];
            let best = dp[i-1][w-cur.w];

            dp[i][w] = notIncludingCur;

            if(w >= cur.w && w-cur.w >= 0 && best + cur.v > dp[i][w]) {
                dp[i][w] = best + cur.v;
            }
        }
    }

    return dp[items.length][maxWeight]
}