效率极高的０／１背包程序
这个程序是我根据一个递归程序改造的．
#define N 5
#define LIMIT 10
int w[20],p[20],max=0;
struct{int top,a[20],sumw[20],lp[20],rp[20];}s;
push(int x,int y,int z){
s.a[++s.top]=x;s.sumw[s.top]=y;s.lp[s.top]=z;} 入栈
pop(int *x,int *y,int *z){
*x=s.a[s.top];*y=s.sumw[s.top];*z=s.lp[s.top--];} 出栈
record(int *rd){int j;
for(j=0;j<=s.top;j++)rd[j]=s.a[j];}
f(int n,int sp,int *b,int l,int *k){int mp1,temp1,temp2,mp=0,sw=0,i=0,x=1;
s.top=-1;
while(s.top>-2){
if(w[i]+sw<=l&&x)
if(i<n-1){push(i,sw,sp);sw+=w[i];i++;}
else {max=sp;record(b);b[*k=s.top+1]=n-1;
temp1=n-1;temp2=s.a[s.top];
while(temp1-temp2==1){temp1=temp2;temp2=s.a[--s.top];} \*此处为我的创意*pop(&i,&sw,&sp);x=0;}
else if(sp-p[i]>max){sp-=p[i];x=1;
if(i<n-1)i++;
else {max=sp;record(b);*k=s.top;pop(&i,&sw,&sp);x=0;}}
else {pop(&i,&sw,&sp);x=0;}}}
main(){int i,j,sp=0,b[20],k;
printf("enter the weight and price");
for(j=0;j<N;j++){scanf("%d",&w[j]);scanf("%d",&p[j]);sp+=p[j];}
f(N,sp,b,LIMIT,&k);
for(i=0;i<=k;i++)printf("%d",b[i]);printf("\n%d",max);}
