【Chapter 5】Dynamic Programming（下）

Dynamic Programming

上一节对矩阵链乘和LCS问题进行了形式化的分析，本节给出矩阵链乘及LCS的伪代码，并给出二者从DP到备忘录版本的转化。

矩阵链乘

Bottom-Up

pseudo code:

Matrix_Chain_Order(p):
	n=p.length-1 //p指的是矩阵规模序列，由上一节的分析知p的长度为矩阵个数+1
	let m[1...n, 1...n] and s[1...n-1,2...n] be new tables
	for i=1 to n:
		m[i,i] = 0 //i=j时，矩阵链仅包含单个矩阵，不需要进行计算
	for l=2 to n:
		//其中，l代表的是矩阵链的长度
		for i=1 to n-l+1:
			//比如，时，n-l+1=3
			j = i+l-1 //j=1+2-1=2
			m[i,j] = INFINITE //将m[i,j]赋予一个很大的初值
			for k=i to j-1: 
				//寻找最优括号化的分裂点
				q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]
				if q<m[i,j]:
					m[i,j] = q
					s[i,j] = k
	return m and s

Top-Down

pseudo code:

Memoized_Matrix_Chain(p):
	n = p.length-1
	let m[1...n, 1...n] be a new table
	for i=1 to n
		for j=1 to n
			m[i,j] = INFINITE //将m数组全部初始化为非常大的数，此后如果
			//m中记录的值小于INFINITE，说明它的值得到了更新，即已经被备忘
	return Lookup_Chain(m,p,1,n)

Lookup_Chain(m,p,i,j):
	if m[i,j] < INFINITE:
		return m[i,j] //如果m[i,j]<INFINITE，说明它已经有备忘录当中的值了，此时剪枝
	if i == j:
		m[i,j] = 0
	else:
		for k=i to j-1:
			q = Lookup_Chain(m,p,i,k) + Lookup_Chain(m,p,k+1,j)
			    + p[i-1]*p[k]*p[j] 
			if q < m[i,j]:
				m[i,j] = q
				//S[i,j] = k
	return m[i,j]

LCS Problem

Bottom-Up

pseudo code:

LCS_Length(X, Y):
	// 相比Matrix Chain，LCS Problem非常的直观易理解
	m = X.length
	n = Y.length
	let b[1...m, 1...n] and c[0...m, 0...n] be new tables
	for i=0 to m:
		c[i][0] = 0
	for j=0 to n:
		c[0][j] = 0
	for i=1 to m:
		for j=1 to n:
			if X[i] == Y[i]:
				c[i][j] = c[i-1][j-1] + 1
				b[i][j] = '↖'
			else if c[i-1][j] > c[i][j-1]:
				c[i][j] = c[i-1][j]
				b[i][j] = '↑'
			else:
				c[i][j] = c[i][j-1]
				b[i][j] = '←'
	return c and b

PRINT_LCS(b, X, i, j):
	// 类似于使用后序遍历的方法求解
	if i == 0 or j == 0:
		return
	if b[i][j] == '↖':
		PRINT_LCS(b, X, i-1, j-1)
		print(X[i])
	else if b[i][j] == '↑':
		PRINT_LCS(b, X, i-1, j)
	else:
		PRINT_LCS(b, X, i, j-1)

Top-Down

下面给出备忘录版本的LCS，伪代码的实现参考了：

1. https://walkccc.me/CLRS/Chap15/15.4/
2. https://blog.csdn.net/weixin_43931548/article/details/106077765

pseudo-code:

LCS_Recur(X, Y, i, j):
	if c[i][j] > -1:
		return c[i][j] //c[i][j]的值已经被备忘，剪枝
	if i ==0 or j == 0:
		return c[i][j] = 0
	if X[i] == Y[j]:
		return c[i][j] = LCS_Recur(X, Y, i-1, j-1) + 1
	return c[i][j] = max(LCS_Recur(X, Y, i-1, j), LCS_Recur(X, Y, i, j-1))

0-1背包

由于0-1背包的相关知识占据了课程的很大部分，涉及动态规划中的0-1背包，贪心算法中的分数背包、0-1背包的2近似算法以及0-1背包的FPTAS算法等，因此在此处对0-1背包在动态规划中涉及到的内容进行记录。

问题描述

给定

n

n

n种物品和一个背包。物品

i

i

i的重量为

w

i

w_i

wi​，价值为

v

i

v_i

vi​，背包的容量为

C

C

C，请问应该如何选择装入背包当中的物品，使得装入背包中的物品的总价值最大？

0-1背包是特殊的整数规划问题：

max

⁡

∑

i

=

1

n

v

i

x

i

\max\sum^n_{i=1}v_ix_i

max∑i=1n​vi​xi​

s

.

t

.

s.t.

s.t.

∑

i

=

1

n

w

i

x

i

≤

C

\sum^n_{i=1}w_ix_i\leq{C}

∑i=1n​wi​xi​≤C

x

i

∈

{

0

,

1

}

,

1

≤

i

≤

n

x_i\in\{0,1\}, 1\leq{i}\leq{n}

xi​∈{0,1},1≤i≤n

建立递归式

对于计科人应该是老生常谈了，经典的二维0-1背包递归式为：

m

(

i

,

j

)

=

max

⁡

{

m

(

i

+

1

,

j

)

,

m

(

i

+

1

,

j

−

w

i

)

+

v

i

}

,

j

≥

w

i

m(i,j)=\max\{m(i+1,j), m(i+1,j-w_i)+v_i\}, j\geq{w_i}

m(i,j)=max{m(i+1,j),m(i+1,j−wi​)+vi​},j≥wi​

m

(

i

,

j

)

=

m

(

i

+

1

,

j

)

,

0

≤

j

<

w

i

m(i,j)=m(i+1,j), 0\leq{j}\lt{w_i}

m(i,j)=m(i+1,j),0≤j<wi​

👆使用二维数组

m

m

m来记录背包当中的状态，其中

i

i

i代表第

i

i

i个物品，而

j

j

j表示当前背包容量，

m

(

i

,

j

)

m(i,j)

m(i,j)表示在背包容量为

j

j

j时，背包中物品的总价值。

第一行代表：如果当前背包容量大于等于第

i

i

i个物品的重量，可以考虑将该物品放入，需要比较将它放入或是不放入哪个价值更高；

第二行代表：当前背包容量已经小于第

i

i

i个物品的重量，无法将物品放入。

算法的时间复杂度为

O

(

n

C

)

O(nC)

O(nC)，但是当

C

>

2

n

C\gt{2^n}

C>2n时，时间复杂度会达到

O

(

n

2

n

)

O(n2^n)

O(n2n)。