## DEV Community 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)