问题
单项选择题
有八种化学药品A、B、C、D、W、X、Y、Z要装箱运输。虽然量不大，仅装1箱也装不满，但出于安全考虑，有些药品不能同装一箱。在下表中，符号“×”表示相应的两种药品不能同装一箱。运输这八种化学药品至少需要装 (54) 箱，实现这种最少箱数的装箱方案(不计装箱顺序)可有 (55) 个。
（55）处填（）。
A．1
B．2
C．3
D．4
答案
参考答案：C
解析：
[分析]： 用图来分析解答这类问题比较直观，判断与计算也不容易遗漏。在图上，用8个节点表示8种药品(为使思考更有条理，8个节点按字母顺序排列)，并将允许同装一箱的两个节点用直线连接起来，如下图所示。
[*]
从上图看出，不可能将4种药品同装一箱(因为不存在4个节点互相都有连接的情况)，最多一箱只能装3种药品(因为存在多个由3个节点互相连接成的三角形)，8种药品至少需要3箱，而且必然是分别装3、3、2种药品(不计装箱顺序)。
允许3种药品同装一箱的实现方法有6种(有6个三角形)：ABW、ABY、BCW、 CWZ、CXZ、DXZ。以字母顺序排列检查，不容易遗漏。
适当选择其中不发生交叉情况的两箱，就能组成6种药品装两箱的方法。剩余的两种药品是否能同装一箱就很容易判断了。这样就形成了如下6种装箱方案。
ABW、CXZ、D、Y
ABW、DXZ、C、Y
ABY、CWZ、DX
ABY、CXZ、D、W
ABY、DXZ、CW
BCW、DXZ、AY
其中有三种方案需要装4箱，有3种方案只需要装3箱。
因此，本题的结论是至少需要装3箱，最优装箱方案有如下3种。
ABY、CWZ、DX
ABY、DXZ、CW
BCW、DXZ、AY