C语言递归详细解答(4)

1如何去掉羞怯那层茧

n总价值为%.2f\n”,maxv);

}

作为对比，下面以同样的解题思想，考虑非递归的程序解。为了提高找解速度，程序不是简单地逐一生成所有候选解，而是从每个物品对候选解的影响来形成值得进一步考虑的候选解，一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况：当该物品被包含在候选解中依旧满足解的总重量的限制，该物品被包含在候选解中是应该继续考虑的；反之，该物品不应该包括在当前正在形成的候选解中。同样地，仅当物品不被包括在候选解中，还是有可能找到比目前临时最佳解更好的候选解时，才去考虑该物品不被包括在候选解中；反之，该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案，程序就去进一步考虑下一个物品。

【程序】

# include <stdio.h>

# define N 100

double limitW;

int cop[N];

struct ele { double weight;

double value;

} a[N];

int k,n;

struct { int flg;

double tw;

double tv;

}twv[N];

void next(int i,double tw,double tv)

{ twv.flg=1;

twv.tw=tw;

=tv;

}

double find(struct ele *a,int n)

{ int i,k,f;

double maxv,tw,tv,totv;

maxv=0;

for (totv=0.0,k=0;k<n;k++)

totv+=a[k].value;

next(0,0.0,totv);

i=0;

While (i>=0)

{ f=twv.flg;

tw=twv.tw;

tv=;

switch(f)

{ case 1: twv.flg++;

if (tw+a.weight<=limitW)

if (i<n-1)

{ next(i+1,tw+a.weight,tv);

i++;

}

else

{ maxv=tv;

for (k=0;k<n;k++)

cop[k]=twv[k].flg!=0;

}

break;

case 0: i--;

break;

default: twv.flg=0;

if (tv-a.value>maxv)

if (i<n-1)

{ next(i+1,tw,tv-a.value);

i++;

}

else

{ maxv=tv-a.value;

for (k=0;k<n;k++)

cop[k]=twv[k].flg!=0;

}

break;

}

}

return maxv;

}



void main()

{ double maxv;

printf(“输入物品种数\n”);

scanf((“%d”,&n);

printf(“输入限制重量\n”);

scanf(“%1f”,&limitW);

printf(“输入各物品的重量和价值\n”);

for (k=0;k<n;k++)

scanf(“%1f%1f”,&a[k].weight,&a[k].value);

maxv=find(a,n);

printf(
“\n选中的物品为\n”);

for (k=0;k<n;k++)

if (option[k]) printf(“%4d”,k+1);

printf(“\n总价值为%.2f\n”,maxv);

}

竹外桃花三两枝，春江水暖鸭先知。老吾老，以