40_初识动态规划

文章目录
  1. 1. 0-1 背包问题
  2. 2. 总结

记录动态规划思想

0-1 背包问题

在满足最大重量的限制前提下,背包中总重量的最大值是多少?

回溯方式解决代码:

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
class Problem01_BackTrace {
var maxW = Int.min // 结果放到 maxW 中
let weight = [2,2,4,6,3]
var n = 5
var w = 9

func maxWeight(i: Int, cw: Int) {
if cw == w || i == n { //cw==w 表示装满了,i==n 表示物品都考察完了
if cw > maxW {
maxW = cw //更新最大值
}
return
}
maxWeight(i: i + 1, cw: cw) ;//选择不装i个物品
if cw + weight[i] <= w {
maxWeight(i: i + 1, cw: weight[i] + cw)
}
}

static func testMaxWeight() {
let problem01Instance = Problem01_BackTrace()
problem01Instance.maxWeight(i: 0, cw: 0)
print(problem01Instance.maxW)
}
}

下面是动态规划方式解决

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
class Problem0_1 {
func knapsack(weight: [Int], n: Int, w: Int) -> Int {//weight: 物品重量,n: 物品个数,w: 背包可承载重量
var states = [[Bool]](repeating: [Bool](repeating: false, count: w+1), count: n)
states[0][0] = true
if weight[0] < w {
states[0][weight[0]] = true
}

for i in 1..<n {
for j in 0...w {
if states[i-1][j] == true {
states[i][j] = states[i-1][j]
}
}
for j in 0...w - weight[i] {
if states[i-1][j] == true {
states[i][j+weight[i]] = true
}
}
}

for i in stride(from: w, through: 0, by: -1) {
if states[n-1][i] == true {
return i
}
}
return 0
}
static func testKnapsack() {
let problem01 = Problem0_1()
let weight = [2,2,4,6,3]
let n = 5
let w = 9

let result = problem01.knapsack(weight: weight, n: n, w: w)
print(result)
}
}

我们把上一层重复的状态(节点)合并,只记录不同的状态,然后基于上一层的状态集合,来推导下一层的状态集合。

下面是思考题杨辉三角的答案

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
class YangHuiTriangle {
let matrix = [[5],[7,8],[2,3,4],[4,9,6,1],[2,7,9,4,5]]
func yanghuiTirangle(_ matrix: [[Int]]) -> Int {
var states = [[Int]](repeating: [Int](repeating: matrix.count, count: 5), count: matrix.count)
states[0][0] = matrix[0][0]
for i in 1..<matrix.count {
for j in 0..<matrix[i].count {
if j == 0 {
states[i][j] = states[i-1][j] + matrix[i][j]
} else if j == matrix[i].count - 1 {
states[i][j] = states[i-1][j-1] + matrix[i][j]
} else {
let top1 = states[i-1][j-1]
let top2 = states[i-1][j]
states[i][j] = min(top1, top2) + matrix[i][j]
}
}
}

var minDis = Int.max
for i in 0..<matrix[matrix.count-1].count {
let distance = states[matrix.count-1][i]
if distance < minDis {
minDis = distance
}
}
return minDis
}
static func testTirangle() {
let triangle = YangHuiTriangle()
let result = triangle.yanghuiTirangle(triangle.matrix)
print(result)
}
}

总结

  1. 贪心:一条路走到黑,就一次机会,只能哪边看着顺眼走哪边
  2. 回溯:一条路走到黑,无数次重来的机会,还怕我走不出来 (Snapshot View)
  3. 动态规划:拥有上帝视角,手握无数平行宇宙的历史存档, 同时发展出无数个未来 (Versioned Archive View)