问答题

问答题 [问题1](8分) 根据[说明]和[C代码]，填充C代码中的空(1)～(4)。

【正确答案】 (1)j＝0 (2)b[j]＝b[j]+s[i] 及其等价形式 (3)min＝temp (4)b[m]＝b[m]+s[i] 及其等价形式

【答案解析】 根据最先适宜算法思想，每取出一个货物，从第一个集装箱开始判断该货物是否能放入集装箱，若能则放入，因此空(1)填i＝0。 while循环判断，若货物不能放入集装箱，则考虑下一个集装箱。不满足while循环中的条件，说明货物能放入集装箱，因此空(2)填b[j]＝b[j]+s[i]。根据最优适宜算法思想，每取出一个货物，从第一个集装箱开始，确定能放入该货物且剩余容量最小的集装箱，并把该货物放入该集装箱中。if条件判断，若找到了比能放入货物且剩余容量更小的集装箱，则剩余容量最小值改为当前的集装箱的剩余容量，因此空(3)填min＝temp。确定了集装箱后，把货物装入集装箱中，空(4)b[m]＝b[m]+s[i]。

问答题 [问题2](4分) 根据[说明]和[C代码]，该问题在最先适宜和最优适宜策略下分别采用了____(5)____和____(6)____算法设计策略，时间复杂度分别为____(7)____和____(8)____(用O符号表示)。

【正确答案】 (5)贪心 (6)贪心 (7)O(n²) (8)O(n²)

【答案解析】 最先适宜算法总是把货物放入第一个能放入的集装箱，最优适宜算法总是把货物放入能容纳该货物且剩余容量最小的集装箱，因此都是基于贪心策略进行的，空(5)和(6)填贪心。函数firstfit中的for循环考虑n个货物，其中嵌套了while循环，最多的集装箱数为n，因此时间复杂度为O(n²)。函数bestfit中的for循环考虑n个货物，其中嵌套了for循环检查每个集装箱的剩余容量，最多的集装箱数为n，因此时间复杂度为O(n²)。

问答题 [问题3](3分) 考虑实例n＝10，C＝10，各个货物的体积为{4，2，7，3，5，4，2，3，6，2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为____(9)____和____(10)____。考虑一般的情况，这两种求解策略能否确保得到最优解?____(11)____(能或否)

【正确答案】 (9)5 (16)4 (11)否

【答案解析】 对实例n＝10，C＝10，S＝{4，2，7，3，5，4，2，3，6，2}，根据最先适宜和最优适宜算法，其具体的装箱方案分别如下图(a)和(b)所示。