动态规划初步.ppt

动态规划初步9155223109动态规划初步
动态规划与分治算法类似,基本思想是将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
两条基本要素:
最优子结构
重叠子问题
设计动态规划算法的步骤:
1、找出最优解的性质,并刻画其结构特征
2、递归的定义最优值
3、以自底向上的方式计算出最优值
4、根据计算最优值时的信息,构造最优解
HDU2084 数塔
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?
最长上升子序列(LCS)
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。
若X=<A, B, C, B, D, A, B>和Y=<B, D, C, A, B, A>,则序列<B, C, A>是X和Y的一个公共子序列,序列<B, C, B, A>也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列,因为X和Y没有长度大于4的公共子序列。
LCS[i][j]记录当A到第i个位置,B到第j个位置时,A、B两个数组的最长公共子序列,那么就会有以下两种情况
当A[i]=B[i]时,说明两个位置的值相等
LCS[i][j]=LCS[i-1][j-1]+1
当A[i]!=B[i]时,说明两个位置的值不相等
LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1])

0-1背包问题
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
使用二维数组f[i][j]:
第一维表示的是:
已经选择到了第i个物品
第二维表示的是:
背包总共使用了j单位
f[i][j]记录的是在这个状态下,所能得到的最大收益
对于每种物品来说,只有两种状态:取或者不取
不取: 对于f[i][j]来说,他的值,应当为f[i-1][j]
因为背包的实际没有增大
取: 对于f[i][j]来说,他的值,应当为f[i-1][j-c[i]]+v[i]
因为背包的实际增大了c[i],价值增加了v[i]
从以上的两种情况,考虑f[i][j]可能由多种情况来,那么就取MAX即可,但是由于有i这意味,那么f[i][j]只能由两种状态来,公式为
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
对于不取的情况而言,值已经存在,并且,我们不能保证当背包容量用尽时是最大值,那么我们就应当扫描所有的背包容量情况。
那么此时的时间复杂度为O(VC),空间复杂度也是O(VC),考虑空间复杂度的降低,我们将f[i][j]中的第一维去掉,只留下背包容量这一维
那么此时的时间复杂度为O(VC),空间复杂度也是O(VC),考虑空间复杂度的降低,我们将f[i][j]中的第一维去掉,只留下背包容量这一维
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};