动态规划算法经典例子

注：本学期刘老师上课内容整理

动态规划

最长递增子序列

在这里插入图片描述输入: 实数序列(x1,x2,…,xn)
输出: xi1 xi2… xik, 其中k最大且i1< i2<… 输入样例: ( 2,8,9,4,6,1,3,7,5,10), OSP?
输出样例: ( 2,4,6,7,10)
穷搜(指数时间?) DP? 子结构? 决策量?
归纳尝试一: 已知[1:i]的1个LIS, 求[1:i+1]的LIS?
假设已知 (2,8,9,4,6,1,3) 的1个LIS (2,8,9), 加入7
7不能加长(2,8,9), 但可加长(2,4,6). 启示,调整?
== 启示: xi+1可能可以使得其它LIS变长 ==
== 调整: 记录尾巴最小的LIS: MTLIS==

归纳尝试二: 知[1:i]的MTLIS, 求[1:i+1]的MTLIS?
假设已知(2,8,9,4) 的MTLIS (2,8,9), 加入6
6不能加长(2,8,9), 但(2,4,6)是新的MTLIS. 启示调整?
启示: xi+1可能可以构成新的MTLIS
调整: 需要记录最长和次长的MTIS
调整: ==需要记录长为k的MTIS: MTIS(k), k=1,2,… ==
归纳尝试三:知[1:i]的MTIS(k), 求[1:i+1]的MTIS(k)
只记录尾巴, 增加父亲标记

输入: 实数序列(x1,x2,…,xn)
输出: xi1 xi2… xik, 其中k最大且i1< i2<… len: 最大长度
 xi+1 < MTIS(1).last
 xi+1  MTIS(len).last
 xi+1  MTIS(s-1).last
xi+1 < MTIS(s).last

归纳三:知[1:i]的MTIS(k), 求[1:i+1]的MTIS(k)
为什么每添加一数只有一个MTIS(k)会改变?
性质: MTIS(1).last  MTIS(2).last  …
证明: 若MTIS(i).last > MTIS(i+1).last, 矛盾.
xi+1改变MTSI (s): MTIS(s-1).last  xi+1 < MTIS(s).last
怎么找修改位置?
==采用二分搜索找s, 时间O(logn)*n. ==

输入: 实数序列(x1,x2,…,xn)
输出: xi1 xi2… xik, 其中k最大且i1< i2<…

1.   数组X, L, F  //X是输入, F[i]: 记录X[i]的父亲//L[i]: X[L[i]]=MTIS(i).last, 即MTIS(i).last的位置 
2.   L[i] = 0, F[i] = 0; L[1] = 1, F[1] = 0, len = 1 //len:最大长度 
3.   对于 i = 2 : n,   // X[L[1]]  X[L[2]]  …  X[L[len]];   X[i]?
4.      若X[L[1]] > X[i],    则  F[i] = 0; L[1] = i.
5.      若X[L[len]]  X[i], 则  F[i] = L[len]; len++; L[len] = i. 
6.      否则  二分搜索L[1:len], 求s使得X[L[s-1]]  X[i] < X[L[s]] 
7.                F[i]=L[s-1]; L[s]=i. 
8.   pt = L[len]; 
9.   对 i = len:1, D[i] = A[pt]; pt = F[pt].  输出D. 

0-1背包问题

输入: n物品重W[1:n], 价值V[1:n], 背包容量C
输出: 装包使得价值最大 (物品重量为整数).
例: W:{2,2,6,5,4},V:{6,3,5,4,6}, C=10?
子结构? 决策量? 递推关系? 最优值?
[1:i], g[i,k] = 由[1:i]组合出重量k的最大价值
（或者说 前i种物品装入重量为k背包的最大价值）
g[i,k] = max{ g[i-1,k], g[i-1,k-W[i]] + V[i] } (OSP)
最优值: g[n,C]

• 0-1背包问题推广 找零钱问题
  一出纳员支付一定数量的现金. 假设他手中有几种面值的硬币，要求他用最少的硬币数支付规定的现金. 例如，现有3种硬币：它们的面值分别为1元、4元和6元. 要支付8元.
  
• 0-1背包问题推广 资源分配问题
  
• （分数）背包问题（knapsack prob)
  
  
• 最优装载
  
  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！