0-1 Knapsack Made Easy

Given a list of items with values and weights, as well as a max weight, find the maximum value you can generate from items where the sum of the weights is less than the max.

Weights = [10, 20, 30]
Values = [60, 100, 120]
Maximum Weight = 50
Weights we can fit into the knapsack = 20 + 30 = 50
So Maximum Value = 100 + 120 = 220

** APPROACH **

------------------ METHOD 1 ------------------
------- RECURSIVE APPROACH -------
This is a TOP DOWN solution : We are starting with the end results in mind and breaking it down into smaller chunks
For each item we gotta decide either we include the item or discard the item ,
we can use recursion to choose every possible combinations that would stay under our maximum weight.
It's gonna take an index

We consider two cases-

1. Include the item
2. Exclude the item

** ------------------ METHOD-1 Source Code------------------ **

function knapsack(weights, values, maxWeight, i) {

   // We reached the last item
    if (i === weights.length) return 0;

    // Item is greater then the max weight : We Skip the item
    if (maxWeight - weights[i] < 0)
        return knapsack(weights, values, maxWeight, i + 1);

    // Compare the results of including and excluding the item
    // We include the current item and add the value
    return Math.max(
        knapsack(weights, values, maxWeight - weights[i], i + 1) + values[i],
        knapsack(weights, values, maxWeight, i + 1)
    );
}

function maxValueGenerator1(weightArray, valueArray, maxWeight) {
    return knapsack(weightArray, valueArray, maxWeight, 0);
}

console.log("RECURSION", maxValueGenerator1([10, 20, 30], [60, 100, 120], 50));

Time Complexity: 0(2^N)
Space Complexity: 0(1)

*------------------ METHOD-2 Source Code ------------------ *
------- MEMOZIATION APPROACH -------

function memoziation(wt, v, W, n, dp) {

    // Base condition
    if (W === 0 || n === 0) return 0;

    // Return the dp if there is no value found
    if (dp[n][W] !== 0) {
        return dp[n][W];
    }

    // Current Item's weight is greater than maximum weight
    if (wt[n - 1] > W) {
        return memoziation(wt, v, W, n, dp)
    } else {
        return dp[n][W] = Math.max(memoziation(wt, v, W - wt[n - 1], n - 1, dp) + v[n - 1], memoziation(wt, v, W, n - 1, dp))
    }

}

function maxValueGenerator1(weightArray, valueArray, maxWeight) {

    // Row
    let dp = new Array(weightArray.length + 1)

    // Initialization
    for (let i = 0; i < dp.length; i++) {

        // Column = Maximum Capcity + 1
        // Initializing Every Row with 0
        dp[i] = new Array(maxWeight + 1).fill(0);

    }

    return memoziation(weightArray, valueArray, maxWeight, weightArray.length, dp);
}

console.log("MEMOZIATION", maxValueGenerator1([10, 20, 30], [60, 100, 120], 50));

Time Complexity: 0(N * W)
Space Complexity: 0(N * W)

------------------ METHOD 3 ------------------
------- DYNAMIC PROGRAMMING APPROACH -------
This is a BOTTOM UP solution : We are start with the sub problems and build up to the final solution
Notes :
Dynamic programming relies on two things :-

Optimal Substructure
Overlapping Sub Problems
5 * 4 MATRIX
Rows - Represents the Index
Comlumns - Weights
Should Go upto the Max weight
Values in the cell - Maximum values
0, 1, 2, 3, 4, 5
0 [ 0, 0, 0, 0, 0, 0 ]
1 [ 0, 0, 0, 0, 0, 0 ]
2 [ 0, 0, 0, 0, 0, 0 ]
3 [ 0, 0, 0, 0, 0, 0 ]
0, 1, 2, 3, 4, 5
0 [ 0, 0, 0, 0, 0, 0 ]
1 [ 0, 6, 6, 6, 6, 6 ]
2 [ 0, 6, 10, 16, 16, 16 ]
3 [ 0, 6, 10, 16, 18, 22 ]
This is How the Dp will look like after Initializing
[
[ 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0 ]
]

** ------------------ METHOD-3 Source Code------------------ **

function maxValueGenerator(weightArray, valueArray, W) {

    // Row --> N + 1
    let dp = new Array(weightArray.length + 1);

    // At this point an empty array is created
    // And Initialized 0th value of the rows and columns with 0
    for (let i = 0; i < dp.length; i++) {

        // Column = Maximum Capcity + 1
        // Initializing Every Row with 0
        dp[i] = new Array(W + 1).fill(0);

    }


    // Note : We don't look at the first row because it is 0
    // We start from index 1 

    // Outer Looping through rows
    for (let i = 1; i <= weightArray.length; i++) {
        for (let j = 0; j <= W; j++) {

            // Two Possible Cases : 
            /* 1. Item is too big and we can't include it
               2. Decide wheather to include it or not 
            */

            // Note : j is the current max weight 

            // Item is greater than maximum weight
            if (weightArray[i - 1] > j) {
                // Set the value as the previous value
                dp[i][j] = dp[i - 1][j]

                // The value will be the maximum value between including and excluding the current item    
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weightArray[i - 1]] + valueArray[i - 1])
            }
        }
    }

    return dp[weightArray.length][W]
}

console.log("Dynammic Programming", maxValueGenerator([10, 20, 30], [60, 100, 120], 50));

Time Complexity: 0(N * W)
Space Complexity: 0(N * W)