[说明2]
[C程序代码2]是能求得“背包问题”的一组解的递归算法程序。“背包问题”的基本描述是:有一个背包,能盛放的物品总重量为S,设有Ⅳ件物品,其重量分别为W1,W2,…,Wn,希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包中,即所选物品的重量之和等于S。
[C程序代码2]
BTREE;
#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) ) )
printf( "4d",w[n] );
return 1 ;
return (2) ;
main ()
if (knap(S,N) )
printf( "OK!\n" );
else
printf ( "N0 ! \n" ) ;
请将[C程序代码2]中空缺处的内容填补完整。
参考答案:knap(s-w[n],n-A)或其等价形式
(B) knap(s,n-A)或其等价形式
解析:递归是设计和描述算法的一种有力工具。能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成一些规模较小的问题,然后由这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并由这些更小问题的解构造出规模稍大问题的解。特别地,当规模N=1时,能直接得到解。递归算法的重点与难点分别如下。
(1) 编写递归程序的关键是:找出问题的递归关系和初始值,可以利用归纳法由一个问题归纳总结出递归式,再加上初始条件,即可编写递归函数。
(2) 编写递归程序时,必须要给出递归结束条件。
(3) 递归的次数不是无限制的,每一次的递归调用都要压栈,占用内存,而计算机的内存是有限的。
(4) 采用递归方法定义的数据结构或问题最适合使用递归方法。
[C程序代码2]用递归算法解决背包问题,解决该问题的思路是对于物品i的选择有两种可能。
(1) 考虑物品i被选择的情况,这种可能性当且仅当包含它不会超过方案总重量的限制时才是可行的。物品i被选择后,继续递归去考虑下一个物品。
(2) 考虑物品i不被选择的情况,这种可能性当且仅当不包含物品f时,也有可能找到价值更大的方案。考虑完物品i后,也要继续递归考虑下一个物品。
根据以上思路分析[C程序代码2]中的函数knap(int s,int n),该函数是用递归算法解决“背包问题”的。其中,参数s为考查完物品i后,背包还能盛放的重量;n为考查完物品i后,下一个待考查的物品。(1) 空缺处是考虑物品n被选择的情况,此时因为物品,n已被选择,所以剩余可盛放的重量应为s-w[n],而背包待考查物品应为n-1,则该空缺处所应填写的内容是“knap(s-w[n],n-1)”。
(2) 空缺处是处理不包含物品i时的情况。由于物品i没有放入背包,则背包可装载重量不变还应是s,而这时应该考虑下一个物品,n-1。因此(2)空缺处所应填写的内容是“knap(s,n-1)”。