0/1背包问题的回溯算法 BackKnap(M,n,W,P,fw,fp,X)/M是背包容量.n件物品,数W[1:n] //和P[l:n]分别表示重量和价值,fw是背包的最后重量,fp是 //背包的最大效益.X[1:n]中美国元素取0或1值.若物品k未放 /入背包,则X[k]=0;否则,X[k]=1 1 integer n,k, Y[l: n], 1, X[l: n] 2 real M, W[1:n], P[l:n], fw, fp, cw, cp: 3cw=0;cp=0;k=1;fp=-1 4 loop 5 while k<n&&cw+W[k]≤Mdo//使用约束函数 cw=cw+W[k]: cp=cp+P[k]; Y[k]=1: k=k+1 endwhile if k>n then 9 p=cp;fw=cw;k=n;X=Y;//修改解 10 else Y[K]=0 11 endif hile Bound(cp, cw, k, M)<fp do while k≠0&&Y[k]≠1do k=k-1 15 endwhile 16 if k=o then return endif Y[K]=0; cw=cw-W[k]: cp=cp-P[k]0/1 背包问题的回溯算法 BackKnap(M,n,W,P,fw, fp,X)//M 是背包容量.n 件物品,数 W[1:n] //和 P[1:n] 分别表示重量和价值,fw 是背包的最后重量,fp 是 //背包的最大效益.X[1:n]中美国元素取 0 或 1 值.若物品 k 未放 //入背包,则 X[k]=0;否则,X[k]=1. 1 integer n,k,Y[1:n],I,X[1:n]; 2 real M,W[1:n],P[1:n],fw,fp,cw,cp; 3 cw=0; cp=0; k=1; fp=-1; 4 loop 5 while k≤n && cw+W[k]≤ M do //使用约束函数 6 cw=cw+W[k]; cp=cp+P[k]; Y[k]=1; k=k+1; 7 endwhile 8 if k>n then 9 fp=cp; fw=cw; k=n; X=Y;//修改解 10 else Y[k]=0; 11 endif 12 while BoundF(cp,cw,k,M)≤fp do 13 while k≠0 && Y[k]≠1 do 14 k=k-1; 15 endwhile 16 if k=0 then return endif 17 Y[k]=0;cw=cw-W[k];cp=cp-P[k];