DP - 01 Knapsack problem

Given an array of weight [w0, w1, w2...] and an array of value [v0, v1, v2...] for some items. Pick some items to fill up a backpack whose maximum capacity is N, with the biggest sum of values.

Note:

  • DP formula is DP[i][j] = max(DP[i-1][j], DP[i-1][j-weight[i] + value[i]).
    • Explanation: Use a 2D array to represent items and weights. DP[i][j] means the max value of selecting items from 0 - i and adding them to a bag whose max capacity is j.
    • There are two situations for item i - pick it or not.
      • Not select i, then the sum of value is the same of selecting from 0 to i-1.
      • Select i, then the sum of value is equal to selecing from 0 to i-1 but substracting the weight of i from the bag.

How to initialize DP:
img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* @param {array} weight
* @param {array} value
* @param {integer} bagWeight
* @return {integer}
**/
function knapsack(weight, value, bagWeight) {
// Create a 2D array and fill it with 0, otherwise you'll get undefined.
let dp = [...Array(weight.length)].map(e => Array(bagWeight+1).fill(0));

// Initialize bags for item 0.
for (let k = weight[0]; k < bagWeight; k++) {
dp[0][k] = value[0];
}

for (let i = 1; i < weight.length; i++) {
for (let j = 0; j <= bagWeight; j++) {
if (j < weight[i]) {
dp[i][j] = dp[i-1][j];
} else {
console.log(dp[i-1][j], dp[i-1][j - weight[i]]);
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]);
}
}
}
return dp[weight.length - 1][bagWeight];
}