∞ ∞ 1 7 8 ∞ 5 1 7 2 ∞ 6 2 5 3 ∞
5．画出当n?4时，0/1背包问题的状态空间树
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 给定背包容量W=10，每件物体的重量以及价值为14（42），6（12），8（40），10（25） ，画出解空间树搜索过程。
四、算法设计题
1．给定数组A[n]，存储n个实数，试设计一个算法，在最坏情况下用最少比较次数找出该数组中元素的最大值和最小值，并说明采用了何种算法设计思想，其最坏比较多少次。 2．描述贪心法的求解过程，给出基于最近邻点策略采用贪心法求解TSP问题伪代码，并分析该算法的时间性能。
3．设计算法实现求数组中相差最小的两个元素（称为最接近数）的差。
4．有n枚硬币，其中有一枚硬币是假币，且假币的重量较轻，通过一架天平找出假币，设计找出假币的方案，要求在最坏情况下用天平的比较次数最少。
5．一个农夫带着一条狼、一只羊和一筐菜，想从河一边（左岸）乘船到另一边（右岸），由于船太小，农夫每次只能带一样东西过河，而且如果没有农夫看管，则狼会吃羊，羊会吃菜。农夫怎样过河才能把每样东西安全地送过河呢？请将这个问题的模型抽象出来，并设计算法求解。
6．已知某系统在通信联络中只可能出现八种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计其哈夫曼编码，并请画出其图形，说明其设计思想。
5
6
7
