动态规划算法.pptVIP

*0-1背包问题求解过程当i=2时：j=1,w(2)=3,jw(2),F2(1)=F1(1)=0;j=2,w(2)=3,jw(2),F2(2)=F1(2)=3;j=3,w(2)=3,j=w(2),F2(3)=max{F1(3),F1(3-3)+v(2)}=max{3,0+4}=4;j=4,w(2)=3,j=w(2),F2(4)=max{F1(4),F1(4-3)+v(2)}=max{3,0+4}=4;j=5,w(2)=3,j=w(2),F2(5)=max{F1(5),F1(5-3)+v(2)}=max{3,3+4}=7;*备忘录表填写：0-1背包问题求解过程ji0123456780000000000100333333320034477773040考虑初始状态是什么？F0(j)=Fi(0)=0*备忘录表填写：0-1背包问题求解过程ji012345678000000000010033333332003447777300345789940考虑初始状态是什么？F0(j)=Fi(0)=0*备忘录表填写：0-1背包问题求解过程ji012345678000000000010033333332003447777300345789940034578910如何从备忘录得出问题的解？*备忘录表填写：0-1背包问题求解过程ji012345678000000000010033333332003447777300345789940034578910如何从备忘录得出问题的解？*1)当Fi(j)=Fi-1(j)时，说明没有选择第i个商品，则回到Fi-1(j)；2)否则：Fi(j)=Fi-1(j-w(i))+v(i)时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到Fi-1(j-w(i))；3)一直遍历到i＝0结束为止，所有解的组成都会找到。寻解方式：*备忘录表填写：0-1背包问题求解过程ji012345678000000000010033333332003447777300345789940034578910第4个选择第3个不选第2个选择第1个不选解：0,1,0,1*动态规划算法:0-1背包问题*动态规划算法:0-1背包问题*X的子序列Z：设序列X,Z,若存在X的元素构成的下标严格递增序列使得，则称Z是X的子序列X与Y的公共子序列Z：Z是X和Y的子序列子序列的长度：子序列的元素个数相关概念3.3.3最长公共子序列LCS*给定序列X=x1,x2,…,xm,Y=y1,y2,…,yn求X和Y的最长公共子序列实例问题描述X:ABCBDABY:BDCABA*给定序列X=x1,x2,…,xm,Y=y1,y2,…,yn求X和Y的最长公共子序列实例问题描述X:ABCBDABY:BDCABA一个最长公共子序列:BCBA*蛮力算法