问答题

试题七
阅读以下说明和C 程序,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
现有n(n < 1000)节火车车厢,顺序编号为1,2,3,...,n,按编号连续依次从A 方向的铁轨驶入,从B 方向铁轨驶出,一旦车厢进入车站(Station)就不能再回到A 方向的铁轨上;一旦车厢驶入B 方向铁轨就不能再回到车站,如图7-1 所示,其中Station 为栈结构,初始为空且最多能停放1000 节车厢。







【参考答案】

(1)InitStack(&station) (2)!IsEmpty(station) (3)state[i]<Top(......

(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)
热门 试题

问答题
用回溯法求解此0-1 背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法,在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往假设已经设计了界函数,判断并剪枝那些即扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v,w,k,W)函数,其中v,w,k 和W 分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得最大的价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。 下面给出0-1 背包问题的回溯法伪代码。 函数参数说明如下: W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。 变量说明如下: cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。 BKNAP(W,n,w,v,fw,fp,X) 1 cw←cp←0 2 (1) 3 fp←-1 4 while true 5 while k≤n and cw+w[k] ≤W do 6 (2) 7 cp←cp+v[k] 8 Y[k] ←1 9 k←k+1 10 if k>n then 11 if fp12 fp←cp 13 fw←cw 14 k←n 15 X←Y 16 else Y(k) ←0 17 while BOUND(cp,cw,k,W) ≤fp do 18 while k≠0 and Y(k) ≠1 do 19 (3) 20 if k=0 then return 21 Y[k] ←0 22 cw←cw-w[k] 23 cp←cp-v[k 24 (4)