41_动态规划理论

文章目录
  1. 1. 一个模型、三个特征
  2. 2. 两种动态规划的解决思路
  3. 3. 思考题的答案

记录动态规划思想

一个模型、三个特征

一个模型:多阶段决策最优模型。解决最优问题,在解决的过程中,需要经历多个决策阶段,每个决策阶段对应一组状态,然后我们寻找一组决策序列,经过这组决策序列,产生最终期望的最优解。

最优子结构:问题的最优解包含子问题的最优解,反过来说,我们可以通过子问题的最优解,推导出问题的最优解。也就是后阶段的状态可以通过前阶段的状态推导出来。

无后效性:推导后面,只需要关心前面状态值,不关心状态怎么推导出来。某阶段的状态一旦确定,就不会受之后阶段的决策影响。

重复子问题:达到某个相同阶段时,可能产生重复的状态

两种动态规划的解决思路

  1. 状态转移表法,:回溯算法实现- 定义状态 - 画递归树、找重复子问题、 话状态转移表- 将填表过程翻译为代码
  2. 状态转移方程法:找最优子结构- 写状态转移方程- 将状态转移方程翻译为代码。

思考题的答案

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
struct Money {
func payMoney() {
//定义输入数据
let values = [1,3,5] //钱币的种类
let pm = 9 //支付金额payMoney

//定义自动变量
let step = pm/values[0] + 1 //定义最大步数
var states = [[Int]](repeating: [Int](repeating: 0, count: pm+1), count: step) //定义状态图

//初始化第一行
for i in 0..<values.count {
states[0][values[i]] = values[i]
}

//每步选择一种钱币,翻译状态图
for i in 1..<step {
for k in 0..<values.count {
for j in 0...pm-values[k] { //行
if states[i-1][j] > 0 {
states[i][j+values[k]] = values[k]
}
}
}
}

for i in 0..<step {
if states[i][pm] > 0 { //找到了
print("找到了一种方案: 使用的币的个数:\(i+1)")
var column = pm
for j in stride(from: i, through: 0, by: -1) {
let currentMoney = states[j][column]
print(currentMoney) //当前币的大小
column -= currentMoney
}
break //退出打印最少币种的方式,不退出打印所有方式。
}
}
}
static func testPayMoney() {
let ins = Money()
ins.payMoney()
}
}