7-动态规划全解.ppt

* LCS-LENGTH(X, Y, m, n) 1 for i ← 1 to m do c[i, 0] ← 0 2 for j ← 0 to n do c[0, j] ← 0 3 for i ← 1 to m do 4 for j ← 1 to n do 5 if xi = yj 6 then c[i, j] ← c[i - 1, j - 1] + 1 7 b[i, j ] ← “↖” 8 else if c[i - 1, j] ≥ c[i, j - 1] 9 then c[i, j] ← c[i - 1, j] 10 b[i, j] ← “↑” 11 else c[i, j] ← c[i, j - 1] 12 b[i, j] ← “←” 13 return c and b 运行时间: ?(nm) * 例子 X = (B, D, C, A, B, A) Y = (A, B, C, B, D, A,B) 0 1 2 6 3 4 5 yj B D A C A B 5 1 2 0 3 4 6 7 D A B xi C B A B 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ? 0 ? 0 ? 0 1 ?1 1 1 ?1 ?1 ? 1 2 ?2 ? 1 ? 1 2 ?2 ? 2 ? 2 1 ? 1 ? 2 ? 2 3 ?3 ? 1 2 ? 2 ? 2 ? 3 ? 3 ? 1 ? 2 ? 3 ? 2 3 4 1 ? 2 ? 2 ? 3 4 ? 4 如果 xi = yj b[i, j] = “ ” 如果 c[i - 1, j]≥c[i, j-1] b[i, j] = “ ? ” 否则 b[i, j] = “ ? ” * 找出最长共同子序列 PRINT-LCS(b, X, i, j) 1 if i = 0 or j = 0 2 then return 3 if b[i, j] = ↖ 4 then PRINT-LCS(b, X, i - 1, j - 1) 5 print xi 6 elseif b[i, j] = ↑ 7 then PRINT-LCS(b, X, i - 1, j) 8 else PRINT-LCS(b, X, i, j - 1) * 例题8：0-1背包问题 小偷有一个可承受W的背包 有n件物品: 第i个物品价值vi 且重wi 目标: 找到xi使得对于所有的xi = {0, 1}, i = 1, 2, .., n,? wixi ? W 并且? xivi 最大 部分背包问题 * 最优子结构 考虑最多重W的物品且价值最高 如果我们把j物品从背包中拿出来 剩下的装载一定是取自n-1个物品使得不超过载重量W – wj并且所装物品价值最高的装载 * 0-1背包问题的动态规划 步骤1 P(i, w) –考虑前i件物品所能获得的最高价值,其中w是背包的承受力 步骤2 阶段分析： P（i，w）＝ P(i-1,w) 当wi w （不够装不装） max P(i-1,w) 够装但不装 p(i-1,w-wi)+pi 够装而且装 对于每一个物品i，都有两种情况需要考虑 第1种情况:物品i的重量wi=w，小偷对物品i可拿或者不拿 P[i,w] = max{P[i-1, w], P[i-1,w-wi] + vi} 第2种情况:物品i的重量wiw,即小偷不拿物品i P(i, w) = P(i - 1, w) * Knapsack (S,W) 1 for w ← 0 to w1 - 1 do P[1, w] ← 0; 2 for w ← w1 to W do P[1, w] ← v1; 3 for i ← 2 to n do 4 for w ← 0 to W do 5 if wi w then 6 P[i,w] ← P[i-1, w]; 7 else 8 P[i,w] ← max{P[i-1, w], P[i-1,w-wi] + vi} 运行时间: ?(nW) * 0-1背包问题的动态规划 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0: n 1 w - wi W i-1 0 first P(i