【说明】 “背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1，w2，…，wn。希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。 如下程序均能求得“背包问题”的一组解，其中程序1是“背包问题”的递归解法，而程序2是“背包问题”的非递归解法。 【程序1】 #include＜stdio.h＞ #define N 7 #define S 15 int w[N+1]={0,1,4,3,4,5,2,7}; int knap(int s, int n) { if(s==0) return 1; if(s＜0 || (s＞0 && n＜1))return 0; if( (1) ){/*考虑物品n被选择的情况*/printf("%4d",w[n]);return 1; } return (2) ;/*考虑不选择物品n的情况*/ } main() { if(knap(S,N))printf("OK!\n"); else printf("N0!\n"); } 【程序2】 #include＜stdio.h＞ #define N 7 #define S 15 typedef struct{int s;int n;int job; }KNAPTP; int w[N+1]={0,1,4,3,4,5,2,7}; int knap(int s, int n); main() {if(knap(S,N)) printf("0K!\n");else printf("N0!\n"); } int knap(int s, int n) {KNAPTP stack[100],x;int top, k, rep;x.s=s;x.n=n;x.job=0;top=1; stack[top]=x; k=0; while( (3) ){x=stack[top];rep=1;while(!k && rep){ if(x.s==0) k=1;/*已求得一组解*/ else if(x.s＜0 || x.n＜=0) rep=0; else{ x.s= (4) ; x.job=1; (5) =x; }}/*while*/if(!k){ rep=1; while(top＞=1 && rep){ x=stack[top--]; if(x.job==1){ x.s +=w[x.n+1]; x.job=2; stack[++top]=x; (6) ; }/*if*/ }/*while*/}/*if*/ /*while*/ if(k){ /*输出一组解*/while(top＞=1){ x=stack[top--]; if(x.job==1)printf("%4d\t",w[x.n+1]);} } return k; }
