5.5动态规划求解0/1背包问题

1.问题描述 背包容量M，n个物品，分别具有效益值P1…Pn,物品重量w1…wn,从n个物品中，选择若干物品放入背包，物品要么整件放入背包，要么不放入。怎样决策可以使装入背包的物品总效益值最大？ 形式化描述： 目标函数： 约束条件： 0/1背包问题：KNAP(1,n,M)

0/1背包问题：M=6,N=3,W=(3,3,4),P=(3,3,5) 贪心法：p3/w3 > p1/w1 > p2/w2 贪心解 ∑P=5（0,0,1） 最优解是：∑P=6（1,1,0）

贪心法求解0/1背包问题不一定得到最优解！ 动态规划求解的问题必须满足最优化原理

2.最优化原理证明 设y1,y2,…,yn是x1,x2,…,xn的0/1值最优序列。 若y1＝0, KNAP(2,n,M)是初始决策产生的状态。则y2,…,yn相对于KNAP(2,n,M)将构成一个最优序列。否则，y1,y2,…,yn将不是KNAP(1,n,M)的最优解 若y1＝1, KNAP(2,n,M－w1)是初始决策产生的状态。则y2,…,yn相对于KNAP(2,n,M－w1)将构成一个最优序列。 否则，设存在另一0/1序列z1,z2,…,zn,使得 且 则序列y1,z2,…,zn将是一个对于KNAP(1,n,M)具有更大效益值的序列。 故，最优性原理成立

3 从前向后求解的递推关系式 记fj(X)是KNAP(1,j,X)的最优解，则fn(M)是KNAP(1,n,M)的最优解 对于fn(M)有： 3 从前向后求解的递推关系式 记fj(X)是KNAP(1,j,X)的最优解，则fn(M)是KNAP(1,n,M)的最优解 对于fn(M)有： fn(M) = max{fn-1(M), fn-1(M-wn)+pn} 对于任意的fi(X)，i＞0,有 fi(X) = max{fi-1(X),fi-1(X-wi)+pi} 第N个物品不放入xn=0 第N个物品放入xn=1

递推过程： ★初始值 0 X≥0 f0（X）= －∞ X＜0 ★f1(X)=max{f0(X),f0(X-W1)+P1} 求出所有可能的X对应的fi值 ★fi(X)=max{fi-1(X),fi-1(X-Wi)+Pi} ★最后求 fn(M)=KNAP(1,n,M)

n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 递推计算过程 －∞ X＜0 f0(X)= fi(X) = max{fi-1(X),fi-1(X-wi)+pi} 4例用动态规划法求解0/1背包问题 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 递推计算过程 －∞ X＜0 f0(X)= 0 X≥0 －∞ X＜0 max{0,－∞+1}=0 0≤X＜2 max{0,0+1} = 1 X≥2 0 0≤X＜2 1 2≤X＜3 max{1,0+2}=2 3≤X＜5 max{1,1+2} = 3 X≥5 f3(M)= max{3,1+5} = 6 f1(X)= f2(X)=

解向量的推导 f3(M)=6 f2(M)<>6 X=(1,0,1) x3=1 ΔP=6-p3=1 ΔM=6-w3=2

fi(x) 5. 0/1背包问题图解过程 1 2 3 4 5 6 7 f0(x)=0 x i:fi-1(x-wi) + pi f0(x)=0 x i:fi-1(x-wi) + pi i=0:函数不存在 1 2 3 4 5 6 7 i＝1:f0(x-w1) + p1 x 1 2 3 4 5 6 7 f1(x) x 1 2 3 4 5 6 7 i＝2:f1(x-w2) + p2 x 1 2 3 4 5 6 7 x f2(x)

● fi-1(X-wi)+pi曲线的构造：将fi-1(X)的曲线在X轴上右移wi个单位，然后上移pi个单位而得到； 2 3 4 5 6 7 8 x 9 i＝3:f2(x-w3) + p3 1 2 3 4 5 6 7 8 x 9 f3(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值， 0≤j＜r} 即Pj=fi(Wj) ● (P0,W0)=(0,0) ●图中有r个阶跃值, 对应r个(Pj,Wj)序偶,1≤j≤r ●图中若Wj＜Wj+1,则Pj＜Pj+1，0≤j＜r ●图中若Wj≤X＜Wj+1，fi(X)=fi(Wj) ●图中若X≥Wr，fi(X)=fi(Wr)

● Si的构造 记 是fi-1(X-wi)+pi的所有序偶的集合，则 其中，Si-1是fi-1的所有序偶的集合 Si的构造：由Si-1和 按照支配规则合并而成。 支配规则：如果Si-1和 之一有序偶(Pj,Wj),另一有(Pk,Wk)， 且有 Wj≥Wk , Pj≤ Pk， 则序偶(Pj,Wj)将被舍弃。 （即取最大值规则）。 初始序偶集合S0={(0,0)}

例2 例1的序偶表示法 S0={(0,0)} ={(1,2)} S1={(0,0),(1,2)} ={(2,3),(3,5)} (w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5) 例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)“支配”而删除 +(1,2) +(2,3) +(5,4)

KNAP(1,n,M)问题的解 ★ Sn是KNAP(1,n,X)在0≤X≤M各种取值下的最优解 xi的推导 xn: 设Sn的最后一对有效序偶是(Pl,Wl)，则 (Pl,Wl)或者是Sn－1的最末一对序偶， 或者是(Pj+pn,Wj+wn)，其中 (Pj,Wj)∈ Sn－1且Wj是Sn－1中满足Wj+wn≤M的最大值。 ● 若(Pl,Wl)∈ Sn－1，则Xn＝0；否则， ● (Pl－pn,Wl-wn)∈ Sn－1 ，Xn＝1 xn-1: 若xn=0，则判断(Pl,Wl)∈ Sn－2？，以确定Xn-1的值 若xn=1，则依据(Pl－pn,Wl-wn)∈ Sn－2？，以判断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)由S3中的序偶(6,6)给出。 1) ∵(6,6) S2 ∴x3=1 2) ∵(6-p3,6-w3)=(1,2)∈S2且(1,2)∈S1 ∴x2=0 3) ∵(1,2) S0 ∴x1=1 因此得到X(1，0，1)

算法1 非形式的背包算法 procedure DKP(p,w,n,M) S0 ←{(0,0)} for i←1 to n-1 do ←{(P1,W1)|(P1-pi,W1-wi)∈ Si-1 and W1≤M} Si ←MERGE-PURGE(Si-1, ) repeat (PX,WX)← Sn-1的最末一个有效序偶 (PY,WY)←(P1＋pn,W1+wn)，其中，W1是Sn-1中使得W＋wn≤M的所有序偶中取最大值的W //沿Sn-1,…, S1回溯确定xn,xn-1,…,x1的取值// if PX＞PY then xn←0 //PX将是Sn的最末序偶// else xn←1 //PY将是Sn的最末序偶// endif 回溯确定xn-1,…,x1 end DKP

7. DKP的实现 1)序偶集Si的存储结构 使用两个一维数组P和W存放所有的序偶(Pl,Wl),其中P存放Pl值，W存放Wl值 ● 序偶集S0, S1,…, Sn-1顺序、连续存放于P和W中； ● 用指针F(i)表示Si中第一个元素在数组 (P,W)中的下标位置，0≤i≤n; ● 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的合并同时进行 设 生成的下一序偶是(PQ,WQ)；对所有的(PQ,WQ)，根据支配规则处理如下： ⑴ 将Si-1中所有W值小于WQ的序偶直接计入Si中； ⑵ 根据支配规则，若Si-1中有W值小于WQ的序偶支配 (PQ,WQ)，则(PQ,WQ)将被舍弃，否则(PQ,WQ)计入Si中；并清除Si-1中所有可被支配的序偶，这些序偶有W≥WQ且P≤PQ ⑶ 对所有的(PQ,WQ)重复上述处理； ⑷ 将最后Si-1中剩余的序偶直接计入Si中； ⑸ 所有计入Si中的新序偶依次存放到由F(i)指示的Si的存放位 置上。 注：不需要存放 的专用空间

3) 算法的实现 0/1背包问题的算法描述 procedure DKNAP(p,w,n,M,m) 3) 算法的实现 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// l←h←1 // S0 的首端和末端；l是Si-1的首端，h是Si-1的末端// F(1)←next←2 //P和W中第一个空位；next指示P/W中可以存放(P,W)序偶的第一个位置// for i←1 to n-1 do //生成Si// k←l u←在l≤r≤h中使得W(r)+wi≤M的最大r //u指示由Si-1生成 的最大有效位置// for j←l to u do //生成 ，同时进行归并// (pp,ww)←(P(j)+pi,W(j)+wi) //生成 中的下一个元素// while k≤h and W(k)＜ww do //从Si-1中取元素并归并// P(next)←P(k);W(next)←W(k) //所有W(k)＜ww 的序偶直接归并// next←next+1;k←k＋1 repeat

//按照支配规则考虑(pp,ww)及Si-1中的序偶// if k≤h and W(k)=ww then pp←max(pp,P(k)) k←k+1 endif if pp＞P(next-1) then (P(next), W(next))←(pp,ww) next←next+1 //清除Si-1中的序偶// while k≤h and P(k)≤P(next-1) do k←k+1 repeat repeat while k≤h do//将Si-1中剩余的元素并入Si // (P(next),W(next))←(P(k),W(k)) next←next+1; k←k+1 //对Si+1置初值 // l←h+1; h←next -1; F(i+1)←next CALL PARTS //递推求取Xn,Xn-1,…,x1// END DKNAP

4. 过程DKNAP的分析 1) 空间复杂度 记Si中的序偶数为：|Si| 则有， |Si|≤ |Si-1|＋| | 故，DKNAP所需的空间复杂度（P、W数组）为:Ο(2n)

且 2) 时间复杂度 由Si-1生成Si的时间为： ，0≤i≤n-1 故，DKNAP计算所有的Si所需的时间为： 注： 若每件物品的重量wi和效益值pi均为整数，则Si中每个序偶(P,W)的P值和W值也是整数，且有 ，W≤M 又，在任一Si中的所有序偶具有互异P值和W值，故有 且

在所有wj和pj均为整数的情况下，DKNAP的时间和空间复杂度将为： 当N很大时，算法的有效性不理想，但是在实际求解效果还是可以的，因为多数情况下P、W都是整数，并且M远小于2n,而且支配规则有效删除Si中的序偶。