什么是动态规划

动态规划是最常用的几大算法类型之一, 其思想可以概括为:

一个多阶段问题可以变换为一系列互相联系的单阶段问题进行解决.

动态规划的原理可以提炼为最优化原理 (Principle of optimality), 即: 对任何一个阶段, 可以形成一个最优决策, 该决策满足: 无论当前阶段的初始状态和初始决策如何, 对于今后的策略而言, 其形成的最终状态必须构成最优策略.

或者反过来: 对最终的最优策略, 其之前的每一个阶段的决策都是最优的, 即全局最优解包含局部最优解.

如果用数学语言描述: 如果一个多阶段问题的最优决策, 可以分解为 n 个单阶段的问题进行决策 (Decision), 且对于任何阶段 k (0<k<n), 无论该阶段的 (即由前 k-1 个决策所形成的) 状态 Sk-1 如何, 可以形成一个策略 Dk, 该策略使得状态 Sk 达到最优化, 那么这个问题可以用动态规划法进行求解.

提炼一下, 最优化原理需要问题满足以下两个核心条件:

  1. 对任何一个阶段, 无论初始状态如何, 都可以形成一个阶段性的最优决策;
  2. 问题的状态, 不会受当前决策之后的决策影响 (无后效性);

动态规划的实现步骤

  1. 划分问题阶段: 将一个问题分解为若干阶段, 大部分问题都满足;
  2. 确定状态描述: 将一个阶段的客观情况用状态加以表示, 注意状态变量必须无后效性, 即不对之后的决策造成影响;
  3. 确定决策逻辑和状态转移方程: 将一个阶段形成最优决策的逻辑加以表示, 并确定决策前后状态发生的变化;
  4. 确定边界条件: 通常决策和状态转移用递推表示, 要确定递推终止的边界条件;

0/1 背包问题

假设有一个容量为 C (capacity) 的背包, 以及一堆 (n 个) 重量 (weight) 为 wi, 价值 (value) 为 vi 的物品, 求解如何在背包中摆放物品, 使得背包中物品的价值最大化.

假设容量为 5kg, 有一个 1kg, 价值 $5 的物品, 一个 2kg, 价值 $10 的物品, 一个 3kg, 价值 $30 的物品, 一个 4kg, 价值 $50 的物品, 那么, 应该在背包中放入 1kg 和 4kg 的物品, 这时背包中物品价值达到最大 ($55).

0/1 背包问题的动态规划法求解

1. 划分问题阶段

乍一看这个问题没有阶段可言, 但实际上我们可以把最终的结果看作物品一个接一个地装入背包的结果, 那么 0/1 背包问题最终可以分解为 n 个阶段, 阶段描述为: 在阶段 k (0<k<n), 在前 k-1 个物品放不放入背包已经确定 ("确定" 的意思是达到了最优解) 的情况下, 对其余 n-k+1 个物品放不放入剩余容量 Ck-1 的背包进行最优决策.

0/1 背包问题的名称由来就是: 该问题可以看作对 n 个物品, 决策不放入 (0) 或放入 (1) 背包的过程.

2. 确定状态描述

显然, 0/1 背包问题中寻求的最优状态, 指背包中物品的价值最大, 在决策第 k 个物品是否放入背包的时候, 我们面临的状态是: 前 k-1 个物品是否放入背包已经确定. 所以状态就是前 k-1 个物品是否放入了背包.

如果采取以上状态描述, 是可以进行动态规划的 (真的可以...), 但观察可以发现, 最核心的状态应该是: 背包当前装入的物品的总价值和背包剩余容量, 之所以采取前 k-1 个物品是否放入背包作为状态, 是因为它决定了背包当前物品价值和剩余容量. 不过要知道, 在动态规划的过程中, 之前的状态不受之后决策的影响, 可以将背包物品价值和剩余容量的计算进行复用, 因此最佳的状态描述是: 前 k-1 个物品形成的最佳决策的结果, 即背包物品价值 Vk 和剩余容量 Ck.

3. 确定决策逻辑和状态转移方程

单阶段的决策逻辑非常简单: 在 Ck-1 已经确定 (即之前 k-1 个物品是否放入背包已经确定) 的情况下, 要决策的问题就是: 是否要把第 k 个物品放入剩余容量 Ck-1 的背包中. 要使当前决策最优, 能采取的只有两种选择:

  1. 不放入第 k 个物品
  2. 放入第 k 个物品

要使状态最优, 只要比较二者的最终价值, 取较大者即可.

状态转移方程:

  1. 如果不放入, 则下一决策的初始状态与当前一致 (因为剩余容量不变);
  2. 如果放入, 则状态变为: Ck-1-wk

0/1 背包问题动态规划法求解的 Go 语言描述

1. 变量定义和测试框架

只关注算法可以略过

package main

import "fmt"

type Item struct {
	Weight int
	Value  int
}

type testCase struct {
	Items    []Item
	Capacity int
	Answer   []int
}

func main() {
	testCases := []testCase{
		// Test cases...
		{[]Item{{1, 2},{2,5}, 2, []int{1}},
	}

	hasError := false

	var caseError bool
	var result []int

	for _, testCase := range testCases {
		caseError = false
		result = packageProblem(testCase.Items, testCase.Capacity)

		fmt.Print(testCase.Items, " put in (", testCase.Capacity, ") -> ", testCase.Answer)

		if len(result) == len(testCase.Answer) {
			for i, v := range result {
				if v != testCase.Answer[i] {
					caseError = true
					break
				}
			}
		} else {
			caseError = true
		}

		if caseError {
			fmt.Print("    Got: ", result)
			hasError = true
		}

		fmt.Print("\n\n")
	}

	// After all test cases finished...
	if hasError {
		fmt.Println("Something Wrong")
	} else {
		fmt.Println("Everything OK")
	}
}

func packageProblem(items []Item, capacity int) []int {
	return []int{}
}

核心算法

不使用多值返回的实现暂未完成

完整算法

0/1 背包问题动态规划法求解的 Go 语言描述 (多值返回)

使用 Go 语言的多值返回, 可以极大简化代码, 有兴趣可以看看, 如下:

func packageProblem(items []Item, capacity int) []int {
	_items = items

	_, decisions := dpStep(len(items)-1, capacity)

	return decisions
}

var _items []Item

func dpStep(i int, capacity int) (int, []int) {
	if i == 0 {
		if capacity < _items[0].Weight {
			return 0, []int{}
		}

		return _items[0].Value, []int{0}
	}

	if capacity-_items[i].Weight < 0 {
		return dpStep(i-1, capacity)
	}

	notPutValue, notPutDecisions := dpStep(i-1, capacity)
	putValue, putDecisions := dpStep(i-1, capacity-_items[i].Weight)
	putValue += _items[i].Value

	if notPutValue > putValue {
		return notPutValue, notPutDecisions
	}
	return putValue, append(putDecisions, i)
}

REFERENCE

Leetcode 常用五大算法思想

算法设计之五大常用算法设计方法

从优化到再优化, 最长公共子串

最长公共序列与最长公共子串