1、5.5动态规划求解0/1背包问题形式化描述：形式化描述：目标函数目标函数：约束条件约束条件：0/1背包问题：背包问题：KNAP(1,n,M)ji1iixpmaxni1,0w,0p,10 xMxwiiini1ii或1.问题描述问题描述背包容量背包容量M，n个物品，分别具有效益值个物品，分别具有效益值P1Pn,物物品重量品重量w1wn,从从n个物品中，选择若干物品放入个物品中，选择若干物品放入背包，物品要么整件放入背包，要么不放入。怎背包，物品要么整件放入背包，要么不放入。怎样决策可以使装入背包的物品总效益值最大？样决策可以使装入背包的物品总效益值最大？v0/1背包问题：背包问题：M=6,N=3,
2、W=(3,3,4),P=(3,3,5)v贪心法：贪心法：p3/w3 p1/w1 p2/w2v贪心解贪心解 P=5（0,0,1）v最优解是：最优解是：P=6（1,1,0）v贪心法求解0/1背包问题不一定得到最优解！v动态规划求解的问题必须满足最优化原理设设y1,y2,yn是是x1,x2,xn的的0/1值最优序列。值最优序列。若若y10,KNAP(2,n,M)是初始决策产生的状态。则是初始决策产生的状态。则y2,yn相对于相对于KNAP(2,n,M)将构成一个最优序列。否则将构成一个最优序列。否则，y1,y2,yn将不是将不是KNAP(1,n,M)的最优解的最优解 若若y11,KNAP(2,n,M
3、w1)是初始决策产生的状态。是初始决策产生的状态。则则y2,yn相对于相对于KNAP(2,n,Mw1)将构成一个最优序列。将构成一个最优序列。否则，设存在另一否则，设存在另一0/1序列序列z1,z2,zn,使得使得 且且 则序列则序列y1,z2,zn将是一个对于将是一个对于KNAP(1,n,M)具有更大具有更大效益值的序列。效益值的序列。故，最优性原理成立故，最优性原理成立niiiwMzw21niniiiiiypzp222.最优化原理证明最优化原理证明3 从前向后求解的递推关系式从前向后求解的递推关系式 记记fj(X)是是KNAP(1,j,X)的最优解，则的最优解，则fn(M)是是KNAP(1
4、,n,M)的最优解的最优解对于对于fn(M)有：有：fn(M)=maxfn-1(M),fn-1(M-wn)+pn 对于任意的对于任意的fi(X)，i0,有有 fi(X)=maxfi-1(X),fi-1(X-wi)+pi第第N个物品不放入个物品不放入xn=0第第N个物品放入个物品放入xn=1 递推过程：递推过程：初始值初始值 0 X00 f0（X）=X0 0 f f1 1(X)=maxf(X)=maxf0 0(X),f(X),f0 0(X-W(X-W1 1)+P)+P1 1 求出所有可能的求出所有可能的X对应的对应的fi值值 f fi i(X(X)=maxf)=maxfi-1i-1(X),f(X
5、),fi-1i-1(X-W(X-Wi i)+P)+Pi i 最后最后求求 fn(M)=KNAP(1,n,M)4例用动态规划法求解例用动态规划法求解0/1背包问题背包问题 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 递推计算过程递推计算过程 X0 f0(X)=0 X0 X0 max0,+1=0 0X2 max0,0+1=1 X2 X0 0 0X2 1 2X3 max1,0+2=2 3X5 max1,1+2=3 X5 f3(M)=max3,1+5=6 fi(X)=maxfi-1(X),fi-1(X-wi)+pif1(X)=f2(X)=解向量的推导解向
6、量的推导 f3(M)=6 f2(M)6 x3=1 P=6-p3=1 M=6-w3=2 X=(1,0,1)f2(M)=1 f1(M)=1 x2=0 x1=15.0/1背包问题图解过程背包问题图解过程i:fi-1(x-wi)+pii=0:函数不存在函数不存在1 2 3 4 5 6 7012i1:f0(x-w1)+p1x1 2 3 4 5 6 7012i2:f1(x-w2)+p23x1 2 3 4 5 6 7012f1(x)x1 2 3 4 5 6 70123xf2(x)1 2 3 4 5 6 7012f0(x)=0 xfi(x)1 2 3 4 5 6 70678x123458 9i3:f2(x-w
7、3)+p31 2 3 4 5 6 70678x123458 9f3(x)10注：注：fi-1(X-wi)+pi曲线的构造：将曲线的构造：将fi-1(X)的曲线在的曲线在X轴上右移轴上右移wi个单个单位，然后上移位，然后上移pi个单位而得到；个单位而得到；fi(X)曲线的构造：由曲线的构造：由fi-1(X)和和fi-1(X-wi)+pi的曲线按的曲线按X相同时相同时取大值取大值的规则归并而成的规则归并而成6.序偶表示法序偶表示法 记记 fi(X)的序偶集合为的序偶集合为 Si=(Pj,Wj)|Wj是是fi曲线中使得曲线中使得fi产生一次阶跃的产生一次阶跃的X值，值，0jr 即即Pj=fi(Wj)
8、(P0,W0)=(0,0)图中图中有有r个阶跃值个阶跃值,对应对应r个个(Pj,Wj)序偶序偶,1jr 图中图中若若WjWj+1,则则PjPj+1，0jr 图中图中若若WjXWj+1，fi(X)=fi(Wj)图中图中若若XWr，fi(X)=fi(Wr)Si的构造的构造 记记 是是fi-1(X-wi)+pi的所有序偶的集合，则的所有序偶的集合，则 其中，其中，Si-1是是fi-1的所有序偶的集合的所有序偶的集合 Si的构造的构造：由：由Si-1和和 按照按照支配规则支配规则合并而成。合并而成。支配规则支配规则：如果：如果Si-1和和 之一有序偶之一有序偶(Pj,Wj),另一有另一有(Pk,Wk)
9、，且有且有 WjWk,Pj Pk，则序偶则序偶(Pj,Wj)将被舍弃。将被舍弃。（即取最大值规则）。（即取最大值规则）。初始序偶集合初始序偶集合S0=(0,0),(|),(11iiiiSwWpPWPSiS1iS1iS1例例2 例例1的序偶表示法的序偶表示法 S0=(0,0)=(1,2)S1=(0,0),(1,2)=(2,3),(3,5)S2=(0,0),(1,2),(2,3),(3,5)=(5,4),(6,6),(7,7)S3=(0,0),(1,2),(2,3),(5,4),(6,6),(7,7)注：序偶注：序偶(3,5)被被(5,4)“支配支配”而删除而删除11S21S31S+(2,3)+(
10、1,2)+(5,4)(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)KNAP(1,n,M)问题的解问题的解 Sn是是KNAP(1,n,X)在在0XM各种取值下的最优解各种取值下的最优解 KNAP(1,n,M)的最优解的最优解由由Sn的最后一对的最后一对有效序偶有效序偶给出。给出。xi的推导的推导 xn:设设Sn的最后一对的最后一对有效序偶有效序偶是是(Pl,Wl)，则，则 (Pl,Wl)或者是或者是Sn1的最末一对序偶，的最末一对序偶，或者是或者是(Pj+pn,Wj+wn)，其中，其中 (Pj,Wj)Sn1且且Wj是是Sn1中满足中满足Wj+wnM的最大值。的最大值。
11、若若(Pl,Wl)Sn1，则，则Xn0；否则，；否则，(Plpn,Wl-wn)Sn1，Xn1 xn-1:若若xn=0，则判断，则判断(Pl,Wl)Sn2？，以确定？，以确定Xn-1的值的值若若xn=1，则依据，则依据(Plpn,Wl-wn)Sn2？，以判断？，以判断Xn-1的值的值 xn-2,x1将依次推导得出将依次推导得出 例例2的解向量推导的解向量推导 S0=(0,0)S1=(0,0),(1,2)S2=(0,0),(1,2),(2,3),(3,5)S3=(0,0),(1,2),(2,3),(5,4),(6,6)M=6，f3(6)由由S S3 3中的序偶中的序偶(6,6)给出。给出。1)(6
12、,6)S1)(6,6)S2 2 x x3 3=1=1 2)(6-p 2)(6-p3 3,6-w,6-w3 3)=(1,2)S)=(1,2)S2 2且且(1,2)S(1,2)S1 1 x x2 2=0=0 3)(1,2)S 3)(1,2)S0 0 x x1 1=1=1因此得到因此得到X(1，0，1)算法算法1 非形式的背包算法非形式的背包算法 procedure DKP(p,w,n,M)S0(0,0)for i1 to n-1 do (P1,W1)|(P1-pi,W1-wi)Si-1 and W1M Si MERGE-PURGE(Si-1,)repeat (PX,WX)Sn-1的最末一个有效序偶
13、的最末一个有效序偶 (PY,WY)(P1pn,W1+wn)，其中，其中，W1是是Sn-1中使得中使得WwnM的所有序偶中取最大值的的所有序偶中取最大值的W /沿沿Sn-1,S1回溯确定回溯确定xn,xn-1,x1的取值的取值/if PXPY then xn0 /PX将是将是Sn的最末序的最末序偶偶/else xn1 /PY将是将是Sn的最末序的最末序偶偶/endif 回溯确定回溯确定xn-1,x1 end DKPiS1iS1 7.DKP的实现1)序偶集序偶集Si的存储结构的存储结构 使用两个一维数组使用两个一维数组P和和W存放所有的序偶存放所有的序偶(Pl,Wl),其中其中P存放存放Pl值，值
14、，W存放存放Wl值值 序偶集序偶集S0,S1,Sn-1顺序顺序、连续连续存放于存放于P和和W中；中；用指针用指针F(i)表示表示Si中第一个元素在数组中第一个元素在数组 (P,W)中的下标位置，中的下标位置，0in;F(n)Sn-1中最末元素位置中最末元素位置1 1 2 3 4 5 6 7 P 0 0 1 0 1 2 3 W 0 0 2 0 2 3 5 F(0)F(1)F(2)F(3)2)序偶的生成与合并序偶的生成与合并 Si的序偶将按照的序偶将按照P和和W的递增次序生成的递增次序生成 中序偶的生成将与中序偶的生成将与 和和Si-1的合并同时进行的合并同时进行 设设 生成的下一序偶是生成的下一
15、序偶是(PQ,WQ)；对；对所有所有的的(PQ,WQ)，根据，根据支配规则处理如下：支配规则处理如下：将将Si-1中所有中所有W值值小于小于WQ的序偶直接计入的序偶直接计入Si中；中；根据支配规则，若根据支配规则，若Si-1中有中有W值小于值小于WQ的序偶的序偶支配支配 (PQ,WQ)，则，则(PQ,WQ)将被舍弃，否则将被舍弃，否则(PQ,WQ)计入计入Si中；中；并清除并清除Si-1中所有可被支配的序偶，这些序偶中所有可被支配的序偶，这些序偶有有WWQWQ且且PPQPPQ 对所有的对所有的(PQ,WQ)重复上述处理；重复上述处理；将最后将最后Si-1中剩余的序偶直接计入中剩余的序偶直接计入
16、Si中；中；所有计所有计入入Si中的新序偶依次存放到由中的新序偶依次存放到由F(i)指示的指示的Si的存放位的存放位 置上。置上。注：不需要存放注：不需要存放 的的专用空间专用空间iS1iS1iS1iS13)算法的实现算法的实现 0/1背包问题的算法描述背包问题的算法描述procedure DKNAP(p,w,n,M,m)real p(n),w(n),P(m),W(m),pp,ww,M；integer F(0:n),l,h,u,i,j,p,next F(0)1;P(1)W(1)0 /S0/lh1 /S0 的首端和末端；的首端和末端；l是是Si-1的首端，的首端，h是是Si-1的末端的末端/F(
17、1)next2/P和和W中第一个空位；中第一个空位；next指示指示P/W中可以存放中可以存放(P,W)序偶的第一个位置序偶的第一个位置/for i1 to n-1 do/生成生成Si/kl u在在lrh中使得中使得W(r)+wiM的最大的最大r /u指示由指示由Si-1生成生成 的最大有效位置的最大有效位置/for jl to u do/生成生成 ，同时进行归并，同时进行归并/(pp,ww)(P(j)+pi,W(j)+wi)/生成生成 中的下一个元素中的下一个元素/while kh and W(k)ww do/从从Si-1中取元素并归并中取元素并归并/P(next)P(k);W(next)W
18、(k)/所有所有W(k)ww 的序偶直接归并的序偶直接归并/nextnext+1;kk1 repeat iS1iS1iS1 /按照支配规则考虑按照支配规则考虑(pp,ww)及及Si-1中的序偶中的序偶/if kh and W(k)=ww then ppmax(pp,P(k)kk+1 endif if ppP(next-1)then(P(next),W(next)(pp,ww)nextnext+1 endif /清除清除Si-1中的序中的序偶偶/while kh and P(k)P(next-1)do kk+1 repeat repeat while kh do/将将Si-1中剩余的元素并入中剩
19、余的元素并入Si/(P(next),W(next)(P(k),W(k)nextnext+1;kk+1 repeat /对对Si+1置初值置初值/lh+1;hnext-1;F(i+1)next repeat CALL PARTS /递推求递推求取取Xn,Xn-1,x1/END DKNAP4.过程过程DKNAP的分析的分析1)空间复杂度空间复杂度 记记Si中的序偶数为：中的序偶数为：|Si|则有，则有，|Si|Si-1|又，又，|Si-1|所以，所以，|Si|22|Si-1|最坏情况下有（由最坏情况下有（由Si-1生成生成 和和Si时没有序偶被支时没有序偶被支配）配）：故，故，DKNAP所需的空间
20、复杂度（所需的空间复杂度（P、W数组）数组）为为:(2(2n n)i1S122|1010nniiniiSi1Si1S2)时间复杂度时间复杂度 由由Si-1生成生成Si的时间为：的时间为：，0iin-1 故，故，DKNAP计算所有的计算所有的Si所需的时间为：所需的时间为：注：注：若每件物品的重量若每件物品的重量wi和效益值和效益值pi均为均为整数整数，则，则Si中每中每个序偶个序偶(P,W)的的P值和值和W值也是整数，且有值也是整数，且有 ，WMM 又，在任一又，在任一Si中的所有序偶具有互异中的所有序偶具有互异P值和值和W值，故有值，故有 且且|)S(|1-i)2(|101nniiSijjpP0|ijjipS0|1|,|min1|0MwSijji 在所有在所有w wj j和和p pj j均为均为整数整数的情况下，的情况下，DKNAPDKNAP的时间和空的时间和空间复杂度将为：间复杂度将为：当当N N很大时，算法的有效性不理想，但是在实际求解效很大时，算法的有效性不理想，但是在实际求解效果还是可以的，因为多数情况下果还是可以的，因为多数情况下P P、W W都是整数，并且都是整数，并且M M远小于远小于2 2n n,而且支配规则有效删除而且支配规则有效删除S Si i中的序偶。中的序偶。),|,2(min1nMpnniin
