这个程序是我根据一个递归程序改造的． #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);}

把代码进行了简化,效率一样:
 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&lt;=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&gt;-2){
if(i&lt;n-1){
  if(w[i]+sw&lt;=l&amp;&amp;x){
      push(i,sw,sp);sw+=w[i];i++;}
  else if(sp-p[i]&gt;max){sp-=p[i];x=1;i++;}
   else {pop(&amp;i,&amp;sw,&amp;sp);x=0;}}
else {record(b);
if(w[i]+sw&lt;=l&amp;&amp;x){b[*k=s.top+1]=n-1;max=sp;temp1=n-1;temp2=s.a[s.top];
while(temp1-temp2==1){temp1=temp2;temp2=s.a[--s.top];}}else{*k=s.top;max=sp-p[i];}
pop(&amp;i,&amp;sw,&amp;sp);x=0;}}}
main(){int i,j,sp=0,b[20],k;
for(i=0;i&lt;20;i++)b[i]=0;
for(j=0;j&lt;4;j++){scanf("%d",&amp;w[j]);scanf("%d",&amp;p[j]);sp+=p[j];}
f(4,sp,b,7,&amp;k);
for(i=0;i&lt;=k;i++)printf("%d",b[i]);printf("\n%d",max);}