0-1背包问题

2020/2/2411.问题描述1)KNAP(1,j,X)目标函数：约束条件：0/1背包问题：KNAP(1,n,M)最优性原理对于0/1背包问题成立求解策略：向前递推、向后递推jiiixp1jiwpxXxwiiijiii1,0,0,101或6.50/1背包问题2020/2/2422)向后的递推求解记fj(X)是KNAP(1,j,X)的最优解，则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}递推过程：★初始值0X≥0f0=－∞X＜0★求出fi在所有可能的X取值情况下的值。★fn(M)=KNAP(1,n,M)2020/2/243例6.11背包问题:n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6递推计算过程－∞X＜0f0(X)=0X≥0－∞X＜0f1(X)=max{0,－∞+1}=00≤X＜2max{0,0+1}=1X≥2－∞X＜0max{0,－∞+2}=00≤X＜2f2(X)=max{1,－∞+2}=12≤X＜3max{1,0+2}=23≤X＜5max{1,1+2}=3X≥5f3(M)=max{3,1+5}=6M=6尽管X≥0,但还不足以装下w1fi(X)是关于X的一个分段函数2020/2/2442235001231f1(X)f2(X)XX2020/2/245解向量的推导：根据特定情况下fi取值的选择情况决定xi的值f3(M)=6x3=1ΔP=6-p3=1KNAP(1,3,6)=6ΔM=6-w3=2X=(1,0,1)f2(ΔM)=1x2=0f1(ΔM)=1x1=12020/2/246f1,f2,f3计算过程的图解1234567012f0(x)=0i:fi-1(x-wi)+pi（装下i物品的情况）i=0:函数不存在1234567012i＝1:f0(x-w1)+p11234567012f1(x)＝max(f0(x),f0(x-w1)+p1)1234567012i＝2:f1(x-w2)+p23xxxx12345670123xf2(x)=max(f1(x),f1(x-w2)+p2)取大值原则2020/2/24712345670678x1234589i＝3:f2(x-w3)+p36781234512345670x89f3(x)=max(f2(x),f2(x-w3)+p3)10注：●fi-1(X-wi)+pi曲线的构造：将fi-1(X)的曲线在X轴上右移wi个单位，然后上移pi个单位而得到；●fi(X)曲线的构造：由fi-1(X)和fi-1(X-wi)+pi的曲线按X相同时f取大值的规则归并而成2020/2/2482.用序偶表示法求0/1背包问题fi是关于X的阶跃函数，阶跃点是fi的关键点。每个阶跃点用其对应坐标表示——称为一个序偶，fi阶跃点的集合称为fi的序偶集合，即：Si={(Pj,Wj)|Wj是fi曲线中使得fi产生一次阶跃的X值，Pj=fi(Wj)，0≤j≤r，r是阶跃点个数}●(P0,W0)=(0,0)●若共有r个阶跃值，则分别对应r个(Pj,Wj)序偶，1≤j≤r●若Wj＜Wj+1,则Pj＜Pj+1，0≤j＜r即fi是关于X的单调递增函数●若Wj≤X＜Wj+1，fi(X)=fi(Wj)即具有阶跃特点●若X≥Wr，fi(X)=fi(Wr)12345670x89f3(x)=max(f2(x),f2(x-w3)+p3)10678123452020/2/249★Si中的序偶是背包问题KNAP(1,i,X)在X各种取值情况下子问题的最优解12345670x89f3(x)=max(f2(x),f2(x-w3)+p3)10678123452020/2/2410Si的构造记是fi-1(X-wi)+pi的所有序偶的集合，则其中，Si-1是fi-1的所有序偶的集合Si的构造：由Si-1和按照支配规则合并而成。支配规则：反映曲线合并过程中的取大值规则。即：如果Si-1和之一有序偶(Pj,Wj),另一有(Pk,Wk)，且有Wj≥Wk,Pj≤Pk，则序偶(Pj,Wj)将被舍弃。}),(|),{(11iiiiSwWpPWPSiS1iS1iS1x1234567012i＝2:f1(x-w2)+p23x1234567012f1(x)＝max(f0(x),f0(x-w1)+p1)即：在Si-1的序偶分量上增加pi、wi生成2020/2/2411例6.12例6.11的序偶计算n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6S0={(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),(8,9)}S3={(0,0),(1,2),(2,3),(5,4),(6,6),(7,7),(8,9)}注：序偶(3,5)被(5,4)“支配”而删除11S21S31S2020/2/2412•在Si中，没有两个完全一样的序偶存在，即不存在i和k，使得(Pj,Wj)、(Pk,Wk)∈Si且Wj＝Wk且Pj＝Pk，同时也不存在Wj＝Wk或Pj＝Pk。•若Wj＞Wk则Pj＞Pk，反之亦然，即序偶同时按照Wi和Pi递增有序。2020/2/2413如何求取决策序列？分析Si中序偶的来源：Si中的序偶或者来源于Si-1或者来源于。★若来源于Si-1，则对当前的W计算fi(X)时，表达式中fi-1(X)的值大些，故第i件物品不装为好，即xi＝0。否则★来源于，fi-1(X-Wi)+Pi的效益值好些，第i件物品应该装入背包，xi＝1。iS1iS1fi(X)=max{fi-1(X),fi-1(X-wi)+pi}2020/2/2414KNAP(1,n,M)问题的解——决策序列的求取★Sn是KNAP(1,n,X)在0≤X≤M各种取值下的最优解★KNAP(1,n,M)的最优解由Sn的最后一对有效序偶(具有有效的最大W值的序偶)给出。xi的推导xn:设Sn的最后一对有效序偶是(P1,W1)，W1≤M，则(P1,W1)或者是Sn-1的最末一对有效序偶，或者是(Pj+pn,Wj+wn)，其中(Pj,Wj)∈Sn-1且Wj是Sn-1中满足Wj+wn≤M的最大值。●若(P1,W1)∈Sn-1，则Xn＝0；否则，●(P1－pn,W1-wn)∈Sn-1，Xn＝1xn-1:若xn=0，则判断Sn-1中(P1,W1)的来源，以确定Xn-1的值若xn=1，则判断Sn-1中(P1－pn,W1-wn)的来源，以确定Xn-1的值xn-2,…,x1将依次推导得出2020/2/2415例6.13（例6.12)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),(7,7),(8,9)}M=6，f3(6)由S3中的序偶(6,6)给出。1)∵(6,6)S2∴x3=12)∵(6-p3,6-w3)=(1,2)∈S2且(1,2)∈S1∴x2=03)∵(1,2)S0∴x1=12020/2/2416算法6.6非形式的背包算法procedureDKP(p,w,n,M)S0←{(0,0)}fori←1ton-1do←{(P1,W1)|(P1-pi,W1-wi)∈Si-1andW1≤M}//生成//Si←MERGE-PURGE(Si-1,)//将Si-1和按支配规则归并为Si//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的取值//ifPX＞PYthenxn←0//PX将是Sn的最末序偶//elsexn←1//PY将是Sn的最末序偶//endif回溯确定xn-1,…,x1endDKPiS1iS1iS1iS12020/2/24173.DKP的实现1)序偶集Si的存储结构使用两个一维数组P和W存放所有的序偶(P,W),其中P存放P值，W存放W值●序偶集S0,S1,…,Sn-1顺序、连续地存放于P和W中；●用指针F(i)表示Si中第一个元素在数组P、W中的下标位置，0≤i≤n;●F(n)＝Sn-1中最末元素位置＋11234567P0010123W0020235F(0)F(1)F(2)F(3)每一部分递增有序2020/2/24182)序偶的生成与合并★Si的序偶将按照P和W的递增次序生成，并且★中序偶的生成将与和Si-1的合并同时进行设生成的下一序偶是(PQ,WQ)，根据支配规则处理如下：⑴将Si-1中所有W值小于WQ的序偶直接计入Si中；⑵根据支配规则，若Si-1中有W值小于WQ的序偶支配(PQ,WQ)，则(PQ,WQ)将被舍弃，否则(PQ,WQ)计入Si中；⑶清除Si-1中所有可被(PQ,WQ)支配的序偶，这些序偶有W≥WQ且P≤PQ；⑷对所有的(PQ,WQ)重复上述处理；⑸将最后Si-1中剩余的序偶直接计入Si中（这是一些P和W均较大的序偶）；所有计入Si中的新序偶依次存放到由F(i)指示的Si的存放位置上。注：不需要存放的专用空间iS1iS1iS1iS12020/2/24193)算法的实现算法6.70/1背包问题的算法描述procedureDKNAP(p,w,n,M,m)realp(n),w(n),P(m),W(m),pp,ww,M；integerF(0:n),l,h,u,i,j,p,nextF(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)序偶的第一个位置//fori←1ton-1do//生成Si//k←lu←在l≤r≤h中使得W(r)+wi≤M的最大r//u指示由Si-1生成的最大有效位置//forj←ltoudo//生成同时进行归并//(pp,ww)←(P(j)+pi,W(j)+wi)//生成中的下一个元素//whilek≤handW(k)＜wwdo//从Si-1中取元素并归并//P(next)←P(k);W(next)←W(k)//所有W(k)＜ww的序偶直接归并//next←next+1;k←k＋1repeatiS1iS1iS1luhnext2020/2/2420//按照支配规则考虑(pp,ww)及Si-1中的序偶//ifk≤handW(k)=wwthenpp←max(pp,P(k))k←k+1endififpp＞P(next-1)then(P(next),W(next))←(pp,ww)next←next+1endif//清除Si-1中的序偶//whilek≤handP(k)≤P(next-1)dok←k+1repeatrepeat//在并入中的所有序偶之后，将Si-1中剩余的元素并入Si//whilek≤hdo(P(next),W(next))←(P(k),W(k))next←next+1;k←k+1repeat//对Si+1置初值//l←h+1;h←next-1;F(i+1)←nextrepeatCALLPARTS//递推求取Xn,Xn-1,…,x1//ENDDKNAP此时W(next-1)≤ww这些序偶的W(k)≥wwiS1lkhnext2020/2/24214.过程DKNAP的分析1)空间复杂度记Si中的序偶数为：|Si|则有，|Si|≤|Si-1|＋||又，||≤|Si-1|所以，|Si|≤2|Si-1|最坏情况下，由Si-1生成以及生成Si时没有序偶被支配，则故，DKNAP所需的空间复杂度（P、W数组）为:Ο(2n)i1S122||1010nniiniiSi1Si1S2020/2/24