问答题 [说明]
“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1，W2，…，Wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于s。
如下程序均能求得“背包问题”的一组解，其中，程序1—8是“背包问题”的递归解法，而程序1-9是“背包问题”的非递归解法。
[程序1—8]
#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")；

[程序1-9]
#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("OK!/n")；
else printf("NO!/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=O；
elsex.s(4)；x.job=1；
(5)=x：


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(k) */输出一组解*/
while(top＞=1)
x=stack[top--]；
if(x.job==1)
printf("M/t, w[x.n+1])；



return k；


【正确答案】knap(s-W[n]，n-1)
【答案解析】
【正确答案】knap(s，n-1)
【答案解析】
【正确答案】top＞=1&&!k或top＞0&&!
【答案解析】
【正确答案】x.s-w[x.n-]
【答案解析】
【正确答案】stack[++top]
【答案解析】
【正确答案】rep=0
【答案解析】[解析] 背包问题是历年试题考得最多的一个经典问题，其可由递归和非递归两种算法实现。不管是递归，还是非递归，程序算法的思路都是先依次考察每个物品，对物品i，考察两种可能情况：首先，考察物品i被选择的情况，这种可能性当且仅当包含它不会超过方案总重量的限制时才是可行的，物品i被选择后，继续考察下一个物品(可采用递归考察或非递归)；其次，考察物品i不被选择的情况，当且仅当不包含物品i时，这种可能性也有可能找到价值更大方案的情况，考察完物品i后，也要继续考察下一个物品(也可采用递归考察或非递归)。
程序1-8用递归算法实现“背包问题”。对每个物品i，考察选择放入和不放入背包两种情况，函数knap(int s，int n)，形参s中是考察完物品i后，背包还能装载的重量；n为考察完物品i后下一个待考察的物品。每次选择一个物品放入背包，那么剩余的物品和背包剩余的重量，又构成一个“背包问题”。分析填空(1)上下的语句，显然是考察物品i放入背包的情况，既然放入背包，则背包剩余可装重量为s w[n]，继续考察物品n 1。因此填空(1)应该是knap(s w[n]，n 1)。
填空(2)显然是处理不包含物品i时的情况。既然物品i(这里为n)没有放入背包，则背包可装载重量当然还是s，而同时应该继续考察下一个物品n 1。不难得出填空(2)应该是knap(s，n 1)。
程序1-9是用非递归算法实现背包问题。程序使用栈(即数组stack表示)来保存到已经考察过的物品。经分析，程序中比较重要的一些变量所表示的功能为：结构变量KNAPTP表示经过考察的物品，其中的分量s表示考察过该物品后，背包所能盛放的物品的重量，分量n表示待考察的下一个物品在数组w中的下标，分量job表示物品当前的状态，job等于1，表示物品n可以放入背包，job等于2，表示物品不能放入背包，那么在以后的选取中，将不再考虑该物品，初始时，job等于0，表示背包中没有放入任何物品；当k=1时，则求得了一组解，可知k为是否求得解的标志，k等于0表示没有解，需继续求解，k等于1表示求得了一组解；rep是一个标志变量，rep等于0，表示结束当前的动作，rep等于1，表示继续进行当前的动作，当栈顶物品不能装入背包时，将rep置为0，表示下一部不再从数组w中取物品，rep初值为1；x为工作结点。
程序开始时将数组中下标最大的物品放入栈中，然后开始考察该物品(栈顶元素出栈)，以后所考察的物品都从栈顶获取。对于填空(3)，当k为1找到解时，则退出while((3))循环，那么可知填空(3)有!k语句，同时考虑到当top=0时，则找不到解，可知填空(3)应该是top＞0&&!k。
while(3)循环体内的语句可以肯定是考察各个物品i(这里为n)的选择情况。分析程序可知，对物品n，程序先考察将物品n放入背包的情况，显然如果物品n满足放入背包的条件，则填空(4)和(5)完成将物品放入背包的操作，其中(4)应该将工作结点x的s分量值减去所考察物品的重量，且n要减去1，修改背包可容纳物品的重量和设置下一个待考察物品，而(5)则需要将修改后的工作结点x送栈顶，将下一个待考察的物品放入栈中。故填空(4)应该是x.s w[x.n ]，填空(5)应该是stack[++top]。
继续往下阅读程序，语句if(!k)后的语句是处理所考察的物品不满足放入背包的条件时的情况(rep=0，while(!k&&rep)循环结束)，则将该物品从背包中取出，修改其job值为2，用以标识该物品不能放入背包，那么在以后的选取中，将不再考虑该物品。修改完成后跳出while(top＞=1&&rep)循环，因此需要将rep置为0，用以结束循环while(top＞=1&&rep)。所以填空(6)应该是rep=0。