数据�l�构�W�三章填�I�题�?qi��ng)参考答案[7]_跨考网

        1�Q�根据需要，用适当的语句填入下面算法的_______中：(x��)�?a target="_blank">北京邮电(sh��)大学 1996 四（10分）�?/span>

　　问题�Q�设�?/span>n件物品，重量分别�?/span>w1,w2,w3,�?/span>,wn和一个能装蝲总重量�ؓ(f��)T的背包。能否从n件物品中选择若干件恰好��它们的重量之和等�?/span>T。若能，则背包问题有解，否则无解。解此问题的���法如下�Q?/span>

　　FUNCTION kanp_stack(VAR stack,w:ARRAY[1..n] OF real; VAR top:integer; T:real):boolean;

　　{w[1�Q?/span>n] 存放n件物品的重量�Q�依�ơ从中取出物品放入背包中�Q�检查背包重量，若不���过T�Q�则装入�Q�否则弃之，取下一个物品试之。若有解则返回函数�?/span>true,否则�q�回false}

　　BEGIN

　　top:=0; i:=1; { i指示待选物�?/span>}

　　WHILE (1)_______ AND(2)_______DO

　　[IF (3)______ OR (4)_______ AND (i<n)

　　THEN [top := (5)_______ ;stack[top] :=i;{�W?/span>i件物品装入背�?/span>}

　　T:=T-w[i]];

　　IF T=0 THEN RETURN ((6)_______) {背包问题有解}

　　ELSE [IF (i=n ) AND (top>0)

　　THEN [i:=(7)_______;{取出栈顶物品}

　　top:= (8)_______ �Q?/span>T:= (9)_______ ]; {恢复T�?/span>}

　　i:=i+1 {准备挑选下一件物�?/span>}

　　];

　　];

　　RETURN((10)_______) {背包无解}

　　END;

　　【参考答案�?/span>

　　�Q?/span>1�Q?/span>T>0�Q?/span>2�Q?/span>i<n�Q?/span>3�Q?/span>T>0�Q?/span>4�Q?/span>top<n�Q?/span>5�Q?/span>top+1�Q?/span>6�Q?/span>true�Q?/span>7�Q?/span>i-1�Q?/span>8�Q?/span>top-1�Q?/span>9�Q?/span>T+w[i]�Q?/span>10�Q?/span>false