GRANT S

●试题四

【答案】（1）knap（s-w［n］，n-1）（2）knap（s，n-1）（3）top>=1 && !k 或 top>0 && k == 0

（4）x.s - w ［x.n--］（5）stack［++top］（6）rep = 0

【解析】试题提供了两种解决问题的方法，程序5.1是用递归的方法来解决背包问题，程序5.2使用非递归的方法来解决背包问题。每次选择一个物品放入背包，那么剩余的物品和背包剩余的重量，又构成一个"背包问题"。程序从数组下标最大的物品开始考查，因此（1）处应该填"knap（s-w［n］,n-1）"，即将数组中第N个物品放入背包，如果它能够放入到背包中，则该物品是构成解的元素之一；否则，将该物品从背包中取出，该物品不构成解的元素，在以后的考查中，它可以被排除，因此（2）处应该填"knap（s,n-1）"。在改程序中用栈来保存已经考查过的物品，结构KNAPTP表示经过考查的物品，s表示考查过该物品后背包所能够盛放的物品的重量；n表示该物品在数组W中的下标；job表示物品当前的状态：当job等于1，表示物品n可以放入背包；job等于2表示物品n不能被放入到背包，那么在以后的选取中将不再考虑该物品。初始时job等于0，表示背包中没有任何放入任何物品。K为有解的标志。Rep为一个标志变量，rep等于0，表示结束当前的动作；rep等于1表示继续进行当前的动作。当栈顶物品不能放入背包时，将rep设置为0，表示下一步不从数组w中取物品。其初值为1。开始时，将数组中下标最大的物品放入栈中，然后开始考查该物品。该物品满足放入背包的条件，第（4）（5）空将完成将物品放入背包的操作，因此（4）空填"x.s-w［x.n--］"，修改背包的可容纳物品的重量；（5）处填"stack［++top］"，将下一个要考查的物品放入栈中。若该物品不满足放入背包的条件，则将该物品从背包中取出，因此将rep置为0，结束循环while（!k&&rep）。将物品从背包中取出，即释放该物品在背包中所占的重量，并标记为不能放入到背包（job=2），再将其放入到栈中；然后继续考查数组w中的下一个物品，因此需要结束循环while（top>=1&&rep），将rep置为0，所以第（6）处应该填"rep=0"。在第三处要求给出循环结束的条件，即可以继续选取物品的条件，在此处填"top>=1&&!k"。