# π€ 0-1 Knapsack Problem | dynamic-programming | javascript

One of the most famous dynamic programming problems. <br /> Use one in geeksforgeeks site, because I couldn't find the exact same problem in leetcode.

## ποΈ Problems

0 - 1 Knapsack Problem | Practice | GeeksforGeeks

``````You are given weights and values of N items,
put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

Note that we have only one quantity of each item.
In other words, given two integer arrays val[0..N-1] and wt[0..N-1]
which represent values and weights associated with N items respectively.
Also given an integer W which represents knapsack capacity,
find out the maximum value subset of val[]
such that sum of the weights of this subset is smaller than or equal to W.
You cannot break an item, either pick the complete item or dont pick it (0-1 property).
``````

If the weight `weight[i]` and `values[i]` of total N items are given, what is the maximum sum of those values which can be added in the total weight limit `W` knapsack bag ?

``````Input:
N = 3
W = 4
values[] = {1,2,3}
weight[] = {4,5,1}
Output: 3
``````

## β¨ Idea

Not the special algorithm but find the maximum value by the full search using `DP` array.

## β¬οΈ bottom-up solution [object Object]

#### π₯³β¬οΈ Think differently

• `dp[n][w]` : `n-th` item, bag weight limit `w` maximum value value.
• basecase value is 0.
• `dp[1...N]` uses 1-indexed array.
``````const dp = Array(N + 1)
.fill(null)
.map((_) => Array(W + 1).fill(0));
``````

#### Not possible case

• When `n-th` item's weight `wt[n-1]` is greater than bag weight limit `w`, we couldn't add `n-th` item.
``````    for (let n = 1; n <= N; n += 1) {
for (let w = 1; w <= W; w += 1) {
if (wt[n - 1] > w) {
dp[n][w] = dp[n - 1][w]
} else {
...
}
}
}
``````

#### Possible case

• Not add `n-th` item : same as `n-1 th` item `dp[n-1][w]`
• Add `n-th` item : previous value `dp[n-1][w - wt[n-1]]`, plus current value `val[n-1]`.
``````for (let n = 1; n <= N; n += 1) {
for (let w = 1; w <= W; w += 1) {
if (wt[n - 1] > w) {
...
} else {
dp[n][w] = Math.max(
dp[n - 1][w],
dp[n - 1][w - wt[n - 1]] + val[n - 1]
)
}
}
}
``````

### β¬οΈ π₯ Solution : bottom-up

``````class Solution {
knapSack(W, wt, val, N) {
const dp = Array(N + 1)
.fill(null)
.map((_) => Array(W + 1).fill(0));

for (let n = 1; n <= N; n += 1) {
for (let w = 1; w <= W; w += 1) {
if (wt[n - 1] > w) {
dp[n][w] = dp[n - 1][w];
} else {
dp[n][w] = Math.max(
dp[n - 1][w],
dp[n - 1][w - wt[n - 1]] + val[n - 1]
);
}
}
}

return dp[N][W];
}
}
``````

## β¬οΈ top-down solution [object Object]

### β¬οΈ π Intuition

#### Base case

If there is no item or knapsack weight limit is less than 0, the final maximum should be 0.

``````    const dp = (n, w) => {
if (n <= 0 || w <= 0) return 0
...
}

return dp(N, W);
``````

#### state transfer function

For the case n-th item, weight `w`:

• (choice1) n-th item is not included:
• it doesn't change both weight and value, so that it is the same as the previous.
``````dp(n, w) = dp(n - 1, w)
``````
• (choice2) n-th item is included:
• n-th item / weight `wt[n-1]` is chosen, the final result can be calculated like the following using the previous one and n-th item's value `val[n-1]`.
``````dp(n, w) = dp(n - 1, w - wt[n - 1]) + val[n - 1]
``````

#### the case which should not be considered

• If the weight of n-th item itself is larger than the weight limit `W`, we couldn't select n-th item or not.
• If so, just return the previous value.
``````    const dp = (n, w) => {
if (n <= 0 || w <= 0) return 0

if (wt[n - 1] > w) {
return dp(n - 1, w)
} else {
...
}
}
}
``````

### β¬οΈ top-down w/o memoization

The top-down solution without the memoization causes the TLE error.

``````class Solution {
knapSack(W, wt, val, N) {
const dp = (n, w) => {
if (n <= 0 || w <= 0) return 0;

if (wt[n - 1] > w) {
return dp(n - 1, w);
} else {
return Math.max(
dp(n - 1, w - wt[n - 1]) + val[n - 1],
dp(n - 1, w)
);
}
};

return dp(N, W);
}
}
``````

### β¬οΈπ₯ Solution : top-down with memoization

Add `cache[]` for memoization.

``````class Solution {
knapSack(W, wt, val, N) {
const cache = {};
const genKey = (n, w) => `\${n}:\${w}`;

const dp = (n, w) => {
const key = genKey(n, w);

if (n <= 0 || w <= 0) return 0;
if (cache[key] !== undefined) return cache[key];

if (wt[n - 1] > w) {
return dp(n - 1, w);
} else {
cache[key] = Math.max(