|
1 | 1 | /** |
2 | | - * @function knapsack |
3 | | - * @description Given weights and values of n (numberOfItems) items, put these items in a knapsack of capacity to get the maximum total value in the knapsack. In other words, given two integer arrays values[0..n-1] and weights[0..n-1] which represent values and weights associated with n items respectively. Also given an integer capacity which represents knapsack capacity, find out the maximum value subset of values[] such that sum of the weights of this subset is smaller than or equal to capacity. You cannot break an item, either pick the complete item or don’t pick it (0-1 property). |
4 | | - * @Complexity_Analysis |
5 | | - * Space complexity - O(1) |
6 | | - * Time complexity (independent of input) : O(numberOfItems * capacity) |
7 | | - * |
8 | | - * @return maximum value subset of values[] such that sum of the weights of this subset is smaller than or equal to capacity. |
9 | | - * @see [Knapsack](https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/) |
10 | | - * @example knapsack(3, 8, [3, 4, 5], [30, 50, 60]) = 90 |
| 2 | + * Solves the 0-1 Knapsack Problem. |
| 3 | + *@param capacity Knapsack capacity |
| 4 | + *@param weights Array of item weights |
| 5 | + *@param values Array of item values |
| 6 | + *@returns Maximum value subset such that sum of the weights of this subset is smaller than or equal to capacity |
| 7 | + *@throws If weights and values arrays have different lengths |
| 8 | + *@see [Knapsack](https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/) |
| 9 | + *@example knapsack(3, [3, 4, 5], [30, 50, 60]) // Output: 90 |
11 | 10 | */ |
| 11 | + |
12 | 12 | exportconstknapsack=( |
13 | 13 | capacity:number, |
14 | 14 | weights:number[], |
15 | 15 | values:number[] |
16 | | -)=>{ |
17 | | -if(weights.length!=values.length){ |
| 16 | +):number=>{ |
| 17 | +if(weights.length!==values.length){ |
18 | 18 | thrownewError( |
19 | | -'weights and values arrays should have same number of elements' |
| 19 | +'Weights and values arrays should have the same number of elements' |
20 | 20 | ) |
21 | 21 | } |
22 | 22 |
|
23 | | -constnumberOfItems=weights.length |
| 23 | +constnumberOfItems:number=weights.length |
24 | 24 |
|
25 | | -//Declaring adata structure to store calculated states/values |
| 25 | +//Initializing a2D array to store calculated states/values |
26 | 26 | constdp:number[][]=newArray(numberOfItems+1) |
27 | | - |
28 | | -for(leti=0;i<dp.length;i++){ |
29 | | -// Placing an array at each index of dp to make it a 2d matrix |
30 | | -dp[i]=newArray(capacity+1) |
31 | | -} |
| 27 | +.fill(0) |
| 28 | +.map(()=>newArray(capacity+1).fill(0)) |
32 | 29 |
|
33 | 30 | // Loop traversing each state of dp |
34 | | -for(leti=0;i<numberOfItems;i++){ |
35 | | -for(letj=0;j<=capacity;j++){ |
36 | | -if(i==0){ |
37 | | -if(j>=weights[i]){ |
38 | | -// grab the first item if it's weight is less than remaining weight (j) |
39 | | -dp[i][j]=values[i] |
40 | | -}else{ |
41 | | -// if weight[i] is more than remaining weight (j) leave it |
42 | | -dp[i][j]=0 |
43 | | -} |
44 | | -}elseif(j<weights[i]){ |
45 | | -// if weight of current item (weights[i]) is more than remaining weight (j), leave the current item and just carry on previous items |
46 | | -dp[i][j]=dp[i-1][j] |
| 31 | +for(letitemIndex=1;itemIndex<=numberOfItems;itemIndex++){ |
| 32 | +constweight=weights[itemIndex-1] |
| 33 | +constvalue=values[itemIndex-1] |
| 34 | +for( |
| 35 | +letcurrentCapacity=1; |
| 36 | +currentCapacity<=capacity; |
| 37 | +currentCapacity++ |
| 38 | +){ |
| 39 | +if(weight<=currentCapacity){ |
| 40 | +// Select the maximum value of including the current item or excluding it |
| 41 | +dp[itemIndex][currentCapacity]=Math.max( |
| 42 | +value+dp[itemIndex-1][currentCapacity-weight], |
| 43 | +dp[itemIndex-1][currentCapacity] |
| 44 | +) |
47 | 45 | }else{ |
48 | | -//select themaximum of (ifcurrentweight is collected thus adding it'svalue) and (if currentweight is not collected thus not adding it's value) |
49 | | -dp[i][j]=Math.max(dp[i-1][j-weights[i]]+values[i],dp[i-1][j]) |
| 46 | +//If the currentitem'sweight exceeds the currentcapacity, exclude it |
| 47 | +dp[itemIndex][currentCapacity]=dp[itemIndex-1][currentCapacity] |
50 | 48 | } |
51 | 49 | } |
52 | 50 | } |
53 | 51 |
|
54 | | -// Return the final maximized value at last position of dp matrix |
55 | | -returndp[numberOfItems-1][capacity] |
| 52 | +// Return the final maximized value atthelast position of the dp matrix |
| 53 | +returndp[numberOfItems][capacity] |
56 | 54 | } |