-
Notifications
You must be signed in to change notification settings - Fork 5
/
DP2.swift
144 lines (132 loc) · 6.33 KB
/
DP2.swift
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//
// DP2.swift
// AlgorithmsSwift
//
// Created by Michael Ho on 12/5/20.
//
class DP2 {
/**
Methods to solve knapsack problems and their variants.
*/
class KnapSack {
/**
The dynamic programming used to calculate knapsack problems. The runtime is O(NW) where N is
the number of objects and W is the weight limit of the knapsack. Note that the runtime is not
polynomial in the input size.
Reference: https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
- Parameter weights: The array represents the values of input objects.
- Parameter values: The array represents the weights of input objects.
- Parameter weightLimit: The total weight allowed.
- Returns: An integer of the maximum value possible given the conditions.
*/
func maxValueWithLimitedSupply(_ weights: [Int], _ values: [Int], _ weightLimit: Int) -> Int {
var dp = Array(repeating: Array(repeating: 0, count: weightLimit + 1), count: weights.count)
for i in 0..<dp.count {
// Each i represents an item in the list.
for w in 0..<dp[i].count {
// w represents weight at each level under weightLimit.
if w == 0 {
// With the weight limit set to 0, there is nothing we can put in.
dp[i][w] = 0
} else if i == 0 {
/**
When we only have one choice, which is item 0, we can only put it in when
its weight is within the limit
*/
dp[i][w] = weights[i] <= w ? values[i] : 0
} else if weights[i] <= w {
/**
If the current item has weight less than the limit, we can choose to include the current item or not
depending on which way let us get the maximum value.
*/
dp[i][w] = max(values[i] + dp[i - 1][w - weights[i]], dp[i - 1][w])
} else {
dp[i][w] = dp[i - 1][w]
}
}
}
return dp.last!.last!
}
/**
The dynamic programming used to calculate knapsack problems with unlimited supply. The runtime is O(NW) where N is
the number of objects and W is the weight limit of the knapsack. The runtime is the same as previous version of
knapsack problem.
- Parameter weights: The array represents the values of input objects.
- Parameter values: The array represents the weights of input objects.
- Parameter weightLimit: The total weight allowed.
- Returns: An integer of the maximum value possible given the conditions.
*/
func maxValueWithUnlimitedSupply(_ weights: [Int], _ values: [Int], _ weightLimit: Int) -> Int {
var maxVal = Array(repeating: 0, count: weightLimit + 1)
for b in 0...weightLimit {
// Calculate for each weight level.
for i in 0..<values.count {
/**
Each i represents an item in the list. We can consider adding the
item if its weight is less than the current weight limit b.
*/
if weights[i] <= b {
maxVal[b] = max(values[i] + maxVal[b - weights[i]], maxVal[b])
}
}
}
return maxVal.last!
}
}
/**
DP and recursive methods to calculate chain multiply matrix problems.
*/
class MatrixMultiply {
/**
The recursive method used to calculate chain multiply matrix problems. Note that an array with N
numbers represents N - 1 matrices, For example, [1, 2, 3, 4] represents 3 matrices 1x2, 2x3 and 3x4.
We set the start to be 1 instead of 0 since the number at index 1 is the one used to multiply the
next matrix in the input.
- Parameter matrices: The array of matrix, refer to the description above for the expressions.
- Parameter start: The start of the serial calculation.
- Parameter end: The tail of the serial calculation.
- Returns: The result of the minimum cost calculation.
*/
func chainMatrixMultiply(_ matrices: [Int], _ start: Int, _ end: Int) -> Int {
if start == end {
return 0
}
var minVal = Int.max;
for l in start..<end {
let count = chainMatrixMultiply(matrices, start, l) + chainMatrixMultiply(matrices, l + 1, end) + matrices[start - 1] * matrices[l] * matrices[end]
minVal = min(minVal, count)
}
return minVal
}
/**
The dynamic programming used to calculate chain multiply matrix problems. Note that the calculation
merely focuses on how to decide which order to perform the multiplication. The runtime is O(N^3)
where N is the number of matrices. For example, input like [10, 20, 30, 40] represents 3 matrices
10x20, 20x30 and 30x40.
Reference: https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/
- Parameter matrices: The array of matrix, refer to the description above for the expressions.
- Returns: The result of the minimum cost calculation.
*/
func dpChainMatrixMultiply(_ matrices: [Int]) -> Int {
let n = matrices.count
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
for i in 1..<n {
dp[i][i] = 0
}
for l in 2..<n {
for i in 1..<n - l + 1 {
let j = i + l - 1
if j == n {
continue
}
dp[i][j] = Int.max
for k in i...j - 1 {
let q = dp[i][k] + dp[k + 1][j] + matrices[i - 1] * matrices[k] * matrices[j];
dp[i][j] = min(q, dp[i][j])
}
}
}
return dp[1][n - 1]
}
}
}