系统采用面向对象方法开发，使用

UML 进行建模。系统的顶层用例图和一次订餐的活动图初稿分别如图 3-1 和图

3-2 所示。
【问题

1】（2 分）

根据【说明】中的描述，给出图

3-1 中 A1 和 A2 所对应的参与者。

【问题

2】（8 分）

根据【说明】中的描述，给出图

3-1 中缺少的四个用例及其所对应的参与者。

【问题

3】（4 分）

根据【说明】中的描述，给出图

3-2 中（1）~（4）处对应的活动名称或图形符号。

【问题

4】（1 分）

指出图

3-1 中员工和顾客之间是什么关系，并解释该关系的内涵。

§
试题四（共
15 分）

阅读下

列说明，回答
问题

1 至问题

2 ，将解答填
入答题纸的对
应栏内。
【说明】

0-1 背包

问题可以描述
为：有

n 个物

品

，

对

i=1 ， 2 ，
… ， n ，第 i
个物品价值为
vi ，重量为
wi （ vi ，和 wi
为非负数），
背包容量为
W （ W 为非
负数），选择
其中一些物品
装入背包，使
装入背包物品
的总价值最大，
即

§ ，且总重

量不超过背包
容量，即

§ ，

其

中

，

∈{0,1} ， xi

=0 表示第 i 个
物品不放入背包，

xi=1 表示第 i 个物品放入背包。

【问题

1】（8 分）

用回溯法求解此

0-1 背包问题，请填充下面伪代码中（1）~（4）处空缺。

回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索

满足约束条件的解。对每一个当前结点，若扩展该结点己经不满足约束条件，则不再继续扩展。为了进一步提高算法的