Lecture 5 Dynamic Programming

Presentation on theme: "Lecture 5 Dynamic Programming"— Presentation transcript:

1 Lecture 5 Dynamic Programming

2 什么是动态规划(dynamic programming)？
动态规划是在研究多阶段决策过程的优化 问题时，把多阶段过程转化为一系列单阶 段问题，利用各阶段之间的关系，逐个求 解，创立了解决这类过程优化问题的新方 法——动态规划。 动态规划程序设计是对解最优化问题的一 种途径、一种方法，而不是一种特殊算法。

3 动态规划术语 重叠子结构、最优子结构 动态规划程序设计是对解最优化问题的一种途径、一 种方法，而不是一种特殊算法。
在ACM里 dp主要关心的是两个 1.状态 2.状态转移方程

4 1.选择状态：／＊将问题发展到各个阶段时所处于的 各种客观情况用不同的状态表示出来。当然，状态的 选择要满足＊／无后效性。
2.确定决策并写出状态转移方程：／＊之所以把这两 步放在一起，是因为决策和状态转移有着天然的联系， 状态转移就是根据上一阶段的状态和决策来导出本阶 段的状态。所以，如果我们确定了决策，状态转移方 程也就写出来了。但事实上，我们常常是反过来做， 根据相邻两段的各状态之间的关系来确定决策。＊ ／  3. 写出规划方程（包括边界条件）：／＊动态规划的 基本方程是规划方程的通用形式化表达式。＊／

5 举个🌰： 在最大连续和问题(在有序的数组中选择连续的一段 使得和最大)中，第一步就是要定义好状态 1.dp[i]表示以i为起点的最大连续和 2.状态转移方程: dp[i]=max(a[i],dp[i+1]+a[i]); 3.确定边界条件： dp[n]=a[n];

6 动态规划－－数字三角形

7 先从小的看起： 右图是一个4层的数字三角形，我们我们要从最上面的3往下走到达底层，每次只能选择下面的两个数的其中之1，问我们可以经过的路径和最大是多少？ 上面红色是一一个可行解。 暴力的思想：在每层里每个点都有2个选择，所以n层的话，我们可以枚举所有的2^n条路径，复杂度O(2^n)

8 dp的思想: 1.定义状态: dp[i][j]表示由第i层第j个往下走到最底层所能获得的最大值 我们最后要求的答案是：dp[1][1] 2.状态转移方程： dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]) 3.边界条件：设最后一层是n dp[n][k]=a[n][k] (1<=k<=n) 复杂度：O(n^2)

9 动态规划－－背包问题 1. 01背包： 有N件物品和一个容量为V的背包。放入第i件 物品所耗的容量为Ci，得到的价值为Wi,问您 最多可以获得多少价值。

10 贪心的策略在这里是失效的： 背包容量为10 A 容量为 7 价值为 单位价值：7/3 B 容量为 4 价值为 单位价值：4/2=2 贪心的策略会先选A，但是不能再选了，所以获得的最大的价值是3 如果先选B，我们可以选两件，因而获得的最大价值为2*2=4 背包问题往往需要动态规划来解决。

11 01背包指的是，每种物品只有两种状态 0（不选）和1（选）。
1.状态：dp[i,v]表示 前i种物品放入一个容量为v的背包里可以获得的最大的价值。我们要求的是dp[n][V]. 2.状态转移方程： dp[i,v]=max(dp[i-1,v],dp[i-1,v-Ci]+Wi); (max里的第一项表示不选该物品，第二项表示选该物品，两种转移途径） 3.边界条件： dp[0,k]=0 (0=<k<=V) 一开始当背包里什么都没装的时候，容量为0,V的背包的价值都为0；

12 状态转移方程的解释： dp[i,v]=max(dp[i-1,v],dp[i-1,v-Ci]+Wi); 前i种物品放在一个容量为v的背包里可以由两种状态转移过来： 一种是前i-1种物品放在一个容量为v的背包里。（即0不选第i个） 一种是选第i个物品，那么所能获得的最大的价值是多少呢？？再往容量为v的背包里塞一个Ci的物品，我们要先预留出Ci的空间，所以我们要考虑剩下的空间v-Ci时的最优子结构，亦即dp[i-1][v-Ci]。再塞进去之后，获得的价值自然时：dp[i-1][v-Ci]+Wi

13 代码： for(int i=0;i<=V;i++) dp[0][i]=0; // 初始条件 for(int i=1;i<=n;i++){ for(int v=0; v<=C[i]-1; v++){ dp[i][v]=dp[i-1][v]; } for(int v=C[i];v<=V;v++){ dp[i][v]=max(dp[i-1][v],dp[i-1][v-C[i]]+W[i]) cout<<dp[n][V]<<endl; 复杂度：O(nV)

14 dp[i][x]=max(dp[i-1][x],dp[i-1][x-C[i]]+W[i])
2 3 … x V i-2 dp[i-2][1] dp[i-2][2] dp[i-2][3] dp[i-2][x] dp[i-2][V] i-1 dp[i-1][1] dp[i-1][2] dp[i-1][3] dp[i-1][x] dp[i-1][V] i dp[i][1] dp[i][2] dp[i][3] dp[i][x] dp[i][x]=max(dp[i-1][x],dp[i-1][x-C[i]]+W[i]) 我们在计算dp[i][x]只会用到dp[i-1][x],dp[i-1][x-C[i]]

15 优化空间复杂度： 我们希望只用一个一维数组去表示状态，dp[x]表示当前容量为x的背包获得的最大价值。（我们省略掉了第i个） dp[i][x]=max(dp[i-1][x],dp[i-1][x-C[i]]+W[i]); dp[x]=max(dp[x],dp[x-C[i]]+W[i]);

16 dp[x]=max(dp[x],dp[x-C[i]]+W[i]);
dp[x-C[i]]和dp[x]都是i-1的时候的量 所以如果我们在转移的时候先转移容量大的背包，再转移容量小的背包，就可以保证方程的正确。

17 第i-1层时的值 dp[0] dp[1] dp[2] dp[3] … dp[x] dp[x+1] dp[V-1] dp[V] 计算dp[i][V],利用dp[i-1][V]和dp[i-1][V-C[i]] dp[0] dp[1] dp[2] dp[3] … dp[x] dp[x+1] dp[V-1] dp[V] 计算dp[i][V－1],利用dp[i-1][V－1]和dp[i-1][V-1-C[i]] dp[0] dp[1] dp[2] dp[3] … dp[x] dp[x+1] dp[V-1] dp[V] 计算dp[i][x+1],利用dp[x+1]和dp[x+1-C[i]] dp[0] dp[1] dp[2] dp[3] … dp[x] dp[x+1] dp[V-1] dp[V]

18 计算dp[i][x],利用dp[x]和dp[x-C[i]]
… dp[x] dp[x+1] dp[V-1] dp[V] 计算dp[i][3],利用dp[3]和dp[3-C[i]] dp[0] dp[1] dp[2] dp[3] … dp[x] dp[x+1] dp[V-1] dp[V] 计算dp[i][2],利用dp[2]和dp[2-C[i]] dp[0] dp[1] dp[2] dp[3] … dp[x] dp[x+1] dp[V-1] dp[V] 计算dp[i][1],利用dp[1]和dp[1-C[i]] dp[0] dp[1] dp[2] dp[3] … dp[x] dp[x+1] dp[V-1] dp[V]

19 计算dp[i][0],利用dp[0]和dp[0-C[i]]
… dp[x] dp[x+1] dp[V-1] dp[V]

20 正过来算的话 dp[0] dp[1] dp[2] dp[3] … dp[x] dp[x+1] dp[V-1] dp[V] dp[0] dp[1] dp[2] dp[3] … dp[x] dp[x+1] dp[V-1] dp[V]

21 上面这么多展示过程，都是想让大家了解今天课程非常重要的一个核心，就是怎么对01背包进行空间上的优化，这对以后做题有着非常大的影响。
代码： for(int i=0;i<=V;i++) dp[i]=0; // 初始条件 for(int i=1;i<=n;i++){ for(int v=V;v>=C[i];v--){ dp[v]=max(dp[v],dp[v-C[i]]+W[i]) } cout<<dp[V]<<endl; 时间复杂度：O(nV) 空间复杂度：O(V)

22 滚动数组： 下面我们来看下另外一个很常用的空间优化技巧，滚动数组。
这个时候我们开的数组时dp[2][V]. 我们来看下利用滚动数组做01背包时的代码： 代码： for(int i=0;i<=V;i++) dp[0][i]=0; // 初始条件 for(int i=1;i<=n;i++){ // v<C[i]的部分省略 for(int v=C[i];v<=V;v++){ dp[i%2][v]=max(dp[(i-1)%2][v], dp[(i-1)%2][v-C[i]]+W[i]) } cout<<dp[n%2][V]<<endl;

23 i dp[0][0] dp[0][1] … dp[0][x] dp[0][x+1] dp[0][V-1] dp[0][V] i+1 dp[1][0] dp[1][1] … dp[1][x] dp[1][x+1] dp[1][V-1] dp[1][V] i+2 dp[0][0] dp[0][1] … dp[0][x] dp[0][x+1] dp[0][V-1] dp[0][V] i+3 dp[1][0] dp[1][1] … dp[1][x] dp[1][x+1] dp[1][V-1] dp[1][V]

24 动态规划－－背包问题 2. 完全背包： 有N件物品和一个容量为V的背包。放入第i件 物品所耗的容量为Ci，得到的价值为Wi,但是 同一件物品可以放入任意多件，问您最多可 以获得多少价值。

25 仍然按原先的思路，我们设状态dp[i][v]为前i种物品放入 容量为v的背包所能获得的最大的价值。
虽然说每件物品能放入无数多件，但是实际上，第i件物 品最多不会放超过 V/w[i] 件 所以可以写出下面的转移方程 dp[i,v]=max{dp[i−1,v−kCi]+kWi |0≤kCi ≤v} 即对放入的数量的每种可能性都考虑一次。这个时候复 杂度就是 V*(V/w[1]+V/w[2]+V/w[3]+…V/w[n]) 这种复杂度往往是我们不能接受的。

26 另外一种思路的转移方程： dp[i][v]=max(dp[i-1][v],dp[i][v-C[i]]＋W[i]) 现在考虑的是完全背包，它同样有两种转移途径，一种 是不选第i个物品，即dp[i-1][v]. 另外一种则是dp[i][v-C[i]]+W[i]。 为什么不是dp[i-1][v-C[i]]+W[i]呢？

27 为什么这个算法就可行呢？首先想想为什么 01 背包中要 按照 v 递减的次序来循环。让 v 递减是为了保证第 i 次循 环中的状态 dp[i,v] 是由状态 dp[i − 1,v − Ci] 递推而来。 换句话说,这正是为了保证每件物品只选一次,保证在考虑 “选入第 i 件物品”这件策 略时,依据的是一个绝无已经 选入第 i 件物品的子结果dp[i − 1, v − Ci]。而现在完全 背 包的特点恰是每种物品可选无限件,所以在考虑“加选 一件第 i 种物品”这种策略时, 却正需要一个可能已选入 第 i 种物品的子结果dp[i, v − Ci ],所以就可以并且必须采 用 v 递增的顺序循环。这就是这个简单的程序为何成立 的道理。

28 完全背包代码： for(int i=0;i<=V;i++) dp[i]=0; // 初始条件 for(int i=1;i<=n;i++){ for(int v=C[i];v<=V;v++){ dp[v]=max(dp[v],dp[v-C[i]]+W[i]) } // 从后往前，保证不改变前面的状态 01背包代码： for(int i=0;i<=V;i++) dp[i]=0; // 初始条件 for(int i=1;i<=n;i++){ for(int v=V;v>=C[i];v++){ dp[v]=max(dp[v],dp[v-C[i]]+W[i]) } // 从前往后，因为恰恰需要的是一个被改变了的状态

29 动态规划－－背包问题 3. 多重背包： 有N件物品和一个容量为V的背包。放入第i件 物品所耗的容量为Ci，得到的价值为Wi,但是 第i件物品最多可以放入Mi件，问您最多可以 获得多少价值。

30 二进制分组的思路： 现在给你15个石子，现在让你把这些石子分成4堆，使得 你可以通过选择其中某几堆凑出0～15的所有数 分成四堆为 时，我们就凑不出4 分成四堆为 时，我们可以凑出任意的数 0=不选 1=1 2=2 3= =4 5= = = =8 9= = =1＋ =4+8 13= ＝ =

31 机智的同学会发现，只要你按二的幂次分总是可以满足 条件的，因为任意一个数都可以由1,2,4,8,16…取和不取 构成。
现在我们来看下1000怎么分 1000＝ ＋489 最后一项并不能凑成512没有影响吗？ 确实没有。 考虑1,2,4,8,16,32,64,128,256，它们的组合能凑出所有 的由0到(1+2+4+…256)的数，即0～511的数。 0~511的数再加上489的这一堆就可以表示出489~1000的 数 0～ ～1000 所以能表示出所有0~1000的数

32 所以对于物品i，虽然它可以选Mi件，但是我们可以将这 Mi件物品按二进制拆分成 logMi 件物品。
像如果某件物品的重量为1，价值为2，数量为1000 我们就可以拆分成： 重量为1，价值为2的物品 重量为2，价值为4的物品 重量为4，价值为8的物品 … 重量为256，价值为512的物品 重量为489，价值为489*2的物品

33 代码(带注释)： for(int i=1;i<＝n;i++){ int num=m[i]; // num为第i件物品由多少件 for(int k=1;num>=0;k*=2){ int mul=min(k,num) //k即为2进制数，之所以要和num取最小就类似与1000的时候512和489的情况，我们要选的时489. for(int j=V;j>=C[i]*mul;j--){ dp[j]=max(dp[j],dp[j-C[i]*mul]+v[i]*mul) } num-=mul; // 分完那堆之后从总数上扣掉

34 代码(不带注释)： for(int i=1;i<=n;i++){ int num=m[i]; for(int k=1;num>=0;k*=2){ int mul=min(k,num) for(int j=V;j>=C[i]*mul;j--){ dp[j]=max(dp[j],dp[j-C[i]*mul]+v[i]*mul) } num-=mul; 复杂度： O(nV*logW)

35 动态规划－－计数问题 在很多情况下的计数，都会存在最优子结构的情况， 所以动态规划就可以利用最优子结构进行恰当的优化。 在这一类问题，状态转移方程就有点像高中学的递推 式，尤其是一维的情况。

36 动态规划－－计数问题 错排数： 1～n的所有全排列，记为a1,a2,a3..an
问：在所有的这些全排列里满足ai != i（1<=i<=n） 的排列有多少种

37 错排数： 1～n的所有全排列里，记为a1,a2,a3..an 问：在所有的这些全排列里满足ai != i（1<=i<=n） 的排列有多少种 D(n) = n! [1/0! - 1/1! + 1/2! - 1/3! + 1/4! (- 1)^n/n!].

38 一种dp的思想，记dp[n]为n个数时候的错排数。
我们考虑两种情况： 现在我们放多一个6 // 显然不合题意 6必须跟前面的某个数互换譬如跟2

39 6还可以和其余的任意5个数互换。对于dp[5]的任意 一个排列，我都可以通过和dp[5]里的5个数交换获得 所以dp[6]=5
6还可以和其余的任意5个数互换。对于dp[5]的任意 一个排列，我都可以通过和dp[5]里的5个数交换获得 所以dp[6]=5*dp[5]+…？ 再考虑另外一种情况，我们固定1～5的某个数，譬如 1 这个时候我们可以发现，通过交换1和6我们可以得到 满足题意的答案：

40 所以我们可以在5个数里固定任意一个数的位置，剩 下的4个数满足错排条件，然后将固定的数和6交换获 得一组符合条件的答案。
5个数里任选一个 所以因子是5 剩下的4个数满足错排 所以因子是dp[4] 所以总共是5*dp[4] dp[6]=5*dp[5]+5*dp[4]

41 所以当我们想通过5个数的情况来计算放多一个6的时 候有两种转移途径：
1.前5个数满足错排关系，多出来的6和和前面5个数 的某个数交换 所以dp[5]*5. 2.前5个数里有一个数不满足错排关系，剩下的四个 数满足错排关系，这个时候只能将多出来的6和那个 不满足的交换。所以式 5*dp[4] 进一步归纳： dp[n]=(n-1)*(dp[n-1]+dp[n-2]);

42 动态规划－－计数问题 拆分数： 对一个给定的数N，你可以将N表示成:
N=a[1]+a[2]+…a[m] a[i]>0,1<=m<=N; 问N有多少种不同的表示方法 f(n) (不考虑顺序) f（n）即为n的拆分数

43 4=4 4=3+1 4=2+2 4=2+1+1 4= 不考虑顺序是指： 4=3+1和4=1+3是一样的，所以不重复计算。

44 5=5 5=4+1 5=3+2 5=3+1+1 5=2+2+1 5= 5=

45 动态规划解题思路： 定义状态：dp[x][n]表示只用整数 1~ x 表示出n有多 少种方法。 状态转移方程： dp[i][n]=dp[i-1][n]+dp[i][n-i] 边界条件： dp[1][k]＝1 (0<=k<=n) 因为对于0~n，只用1去表示的只有一种方法。

46 这道题也叫整数的无序拆分数。它的解法有非常多， 动态规划是其中的一种。
还有利用母函数的方法，复杂度大致是O(n^3) 运用五边形数定理，复杂度可以降到O(n^1.5)

47 总结 动态规划中的背包问题是基础而且重要的。 动态规划可以很复杂。dp[i][j][k] dp[i][j][k][l]都是有 可能的。
动态规划的应用很广。树dp,图dp,状态压缩dp,数位 dp，插头dp… 动态规划是思想不是具体的算法。

48 Thank you!