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

1如何去掉羞怯那层茧

归去考虑其余物品的选择。

（2） 考虑物品i不被选择，这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。

按以上思想写出递归算法如下：

try(物品i，当前选择已达到的重量和，本方案可能达到的总价值tv)

{ /*考虑物品i包含在当前方案中的可能性*/

if(包含物品i是可以接受的)

{ 将物品i包含在当前方案中；

if (i<n-1)

try(i+1,tw+物品i的重量,tv);

else

/*又一个完整方案，因为它比前面的方案好，以它作为最佳方案*/

以当前方案作为临时最佳方案保存;

恢复物品i不包含状态；

}

/*考虑物品i不包含在当前方案中的可能性*/

if (不包含物品i仅是可男考虑的)

if (i<n-1)

try(i+1,tw,tv-物品i的价值)；

else

/*又一个完整方案，因它比前面的方案好，以它作为最佳方案*/

以当前方案作为临时最佳方案保存;

}

为了理解上述算法，特举以下实例。设有4件物品，它们的重量和价值见表：

物品 0 1 2 3

重量 5 3 2 1

价值 4 4 3 1



并设限制重量为7。则按以上算法，下图表示找解过程。由图知，一旦找到一个解，算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解，算法不会在该分支继续查找，而是立即终止该分支，并去考察下一个分支。



按上述算法编写函数和程序如下：

【程序】

# include <stdio.h>

# define N 100

double limitW,totV,maxV;

int option[N],cop[N];

struct { double weight;

double value;

}a[N];

int n;

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

{ int k;

/*考虑物品i包含在当前方案中的可能性*/

if (tw+a.weight<=limitW)

{ cop=1;

if (i<n-1) find(i+1,tw+a.weight,tv);

else

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

option[k]=cop[k];

maxv=tv;

}

cop=0;

}

/*考虑物品i不包含在当前方案中的可能性*/

if (tv-a.value>maxV)

if (i<n-1) find(i+1,tw,tv-a.value);

else

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

option[k]=cop[k];

maxv=tv-a.value;

}

}



void main()

{ int k;

double w,v;

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

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

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

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

{ scanf(“%1f%1f”,&w,&v);

a[k].weight=w;

a[k].value=v;

totV+=V;

}

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

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

max
v=0.0;

for (k=0;k<n;k++) cop[k]=0;

find(0,0.0,totV);

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

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

printf(“\