问答题
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W
1
，W
2
，…，W
n
。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，W(i=1，2，…，n)均为正整数，并已顺序存储在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。
Knap(S，n)
若S=0
则Knap←true
否则若(S<0)或(S>0且n<1)
则Knap←false
否则若Knap(1)，=true
则print(w[n])；Knap←true
否则Knap+-Knap(2) ，
【山东工业大学1996五(10分)1998二、1(4分)】
【正确答案】正确答案：若第n件物品能放入背包，则问题变为能否再从n一1件物品中选出若干件放入背包(这时背包可放入物品的重量变为s—w[n])。若第n件物品不能放入背包，则考虑从n一1件物品选若干件放入背包(这时背包可放入物品仍为s)。若最终s=0，则有一解；否则，若s<0或虽然s>0但物品数n<1，则无解。 (1)s—W[n]，n一1 ／／Knap(s—W[n]，n一1)=true (2)S，n一1 ／／Knap*--Knap(s，n一1)
【答案解析】