-
Notifications
You must be signed in to change notification settings - Fork 1
/
01KnapsackProblem_3.ts
53 lines (46 loc) · 2.45 KB
/
01KnapsackProblem_3.ts
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
* Solve the knapsack problem by maximizing the total profit while keeping the total items choosen to remain within the total capacity allocated.
* Use of dynamic programming using the memoization techniques.
* Complexity: Time = O(N * C) since at max with DP, we will compute the function of the product of capacity and items in the worst case.
* Complexity: Space = O(N * C) since that the memoization table size. O(N) for the recursion.
* Table of [items idx][capacity]
*
* @param profits
* @param weights
* @param capacity
*/
function findMaxProfitDPTable(profits: number[], weights: number[], capacity: number) {
const netProfits: number[][] = Array.from({length: weights.length}, () => Array(capacity + 1).fill(0))
// Initialize the net profits for all the capacities with 0 items to be 0.
for(let idx = 0; idx < weights.length; idx++) {
netProfits[idx][0] = 0
}
// Initialize the net profits for all the capacities with only 1 item to be the same as the item.
for (let cap = 1; cap <= capacity; cap++) {
if (weights[0] <= cap) netProfits[0][cap] = profits[0]
}
// Build the DP table for each item index to be included with all the capacities possible from 0 to total capacity.
for (let idx = 1; idx < weights.length; idx++) {
for (let cap = 1; cap <= capacity; cap++) {
/**
* For each index of the available items and for each possible capacity, we calculate the new profit achievable.
* Each item index means inclusion of one or more items till the index level.
* Each capacity indicates the maximum capacity that is allowed to be filled till now.
*/
let profitWithInclusion = 0
if (cap >= weights[idx]) {
profitWithInclusion = netProfits[idx - 1][cap - weights[idx]] + profits[idx]
}
netProfits[idx][cap] = Math.max(profitWithInclusion, netProfits[idx - 1][cap])
}
}
return netProfits[weights.length - 1][capacity];
}
// Test Cases
function runTestDPTable(profits: number[], weights: number[], capacity: number) {
console.log(`Max Profit using the profits: ${profits}, weights: ${weights}, capacity: ${capacity} = ${findMaxProfitDPTable(profits, weights, capacity)}`);
}
runTestDPTable([1, 6, 10, 16], [1, 2, 3, 5], 7);
runTestDPTable([1, 6, 10, 16], [1, 2, 3, 5], 6);
runTestDPTable([1, 6, 10, 16], [1, 2, 3, 5], 1);
runTestDPTable([1, 6, 10, 16], [1, 2, 3, 5], 2);