发布时间 : 星期日 文章第7章算法程序与计算系统之灵魂练习题答案解析更新完毕开始阅读8757ab91a300a6c30c229fc8
由题意可知使用贪心算法，从单位价值最高的开始放入，五个物品单位价值从大到小依次为：2.5,2,1,1,1/3，依次放入并验证是否超出背包重量限制：$10-4kg, $2-1kg,$1-1kg,$2-2kg，之后放不下$4-12kg的物品，到此总价值是15，所以选择（B）。
具体内容查阅背包问题相关资料。
(4) 假定求解该问题的一种贪心策略是：最大程度地利用背包的容量（15kg），依据该算法策略所得到的解的总价值是_____。
(A) 8 (B) 15 (C) 14 (D) 13
答案：A 解释：
本题考查问题及其数学建模的作用
由题意可知使用贪心算法，需要让剩余空间最小，那么可以得到的组合是，12kg+2kg+1kg=15kg，重量得到最大利用，总价值是8，所以选择（A）。
具体内容查阅背包问题相关资料。
(5) 使用遍历算法策略所得到的解的总价值是_____。
(A) 8 (B) 15 (C) 14 (D) 13
答案：B 解释：
本题考查问题及其数学建模的作用
用遍历算法策略，状态转移方程：f[v]=max{f[v],f[v-c[i]]+w[i]}，即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值，第i件物品的重量是c[i]，价值是w[i]。“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第 i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放 入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。按此方法，可得总价值是15，所以选择（B）。
具体内容查阅背包问题相关资料。
(6) 假定有N个物品，其价值分别为V1, V2, ..., VN，重量分别为W1, W2, ..., WN，背包所能承受的总重量为Wmax，为物品i定义一个决策变量xi，其中xi=1表示选择该物品，xi=0表示不选择该物品。下面哪个描述共同构成了该问题的数学模型_____。
(A) 问题的目标函数是max ?xV；
iii?1NiiN(B) 问题的目标函数是max ?xW；
i?1(C) 问题解所应满足的约束是 ?xW?Wiii?1NNmax；
(D) 问题解所应满足的约束是 ?xVi?1ii?Wmax；
(E) 前述(A)和(C)； 答案：E 解释：
本题考查问题及其数学建模的作用 该问题有两个条件：
1）物品不能超过背包所能承受的重量，即（C）选项： ?xW?Wiii?1Nmax
2）背包内物品价值最大，即（A）选项目标函数为
max ?xiVii?1N
（B）和（D）选项明显错误，将质量和价值比较。
所以选择（E）。
具体内容查阅背包问题相关资料。
4、TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答下列问题。
(1)关于TSP问题的遍历算法和贪心算法，下列说法正确的是_____。
(A)对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是贪心算法更快一些，而遍历算法更慢一些；
(B)对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是遍历算法更快一些，而贪心算法更慢一些；
(C)对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解，执行更快一些，而遍历算法是求精确解，执行更慢一些；
(D)对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求精确解，执行更快一些，而遍历算法是求近似解，执行更慢一些；
答案：C 解释：
本题考查对贪心算法与遍历算法的简单理解
贪心算法：一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。如果以A城市为起点，选择最近的下一点，为B城市。以B城市为起点，选择最近的下一个城市，可以选择C或D，以选择D为例。以D为起点，选择最近的下一点，为C城市。最后回到A。整个过程的花费为：14。于是，该贪心算法的解为14。而通过遍历可知，该问题的最优解为A-B-C-D-A，花费为13。可见，贪心算法与遍历算法的解不会总是完全相同。而贪心
3
算法只会做当前情况下最优选择，其时间复杂度为n级别。而遍历则会将各种情况考虑在内，其时间复杂度为（n-1）！级别当城市的数量变多时，遍历算法将会出现组合爆炸。故，相比之下，贪心算法的计算速度更快。所以(C)选项是正确的。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)关于TSP，下列说法不正确的是_____。
(A)TSP问题的一个可能解就是n个城市的一个组合
都对应不同的城市。若要求得最优解，则必须对所有的组合，即所有可能解进行比较。
(B)TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，以致于计算机不能在有限时间内完成所有的组合；
(C)TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，虽如此，计算机仍然能够在有限时间内完成所有的组合；
(D)上述思想--对所有组合进行比较的思想，即是所谓的遍历算法策略，它仅仅对n值很小的TSP问题是能行的。
答案：C 解释：
本题考查对TSP组合优化问题的理解
对所有组合进行比较的思想，即所谓的遍历算法策略，其组合数目为n!。2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。由此可见，当n巨大时，用遍历算法解决TSP问题是不现实的。所以(C)选项错误。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(3)关于TSP的贪心算法的求解思想，下列说法不正确的是_____。
(A)无需对所有组合(所有可能解)进行比较，而仅需依照某种办法确定其中的一个组合即可，该组合不一定是最优解，但却是一个较优解或次优解；
(B)在确定一个组合
(C)贪心算法确定的路径，是由局部最优(即tk+1在tk看来是最优的)组合起来的路径，该
路径从全局角度也一定是最优的；
(D)对一个具体的TSP问题，每次执行贪心算法，所求得的最终解可能是不同的。
答案：C 解释：
本题考查对TSP贪心算法的理解
（A）(B)选项都是对贪心算法的描述，贪心算法的核心就是：只考虑当前情况下得最优解。故（A）（B）正确。贪心算法得到的解释可行解，但不一定是最优解，故(C)错误。在执行贪心算法的过程中，会遇到下一步有两个最优选项的情况，所以每次执行贪心算法的最终解的结果可能是不同的。故(D)正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(4)下列哪些问题可应用求解TSP的算法，正确的是_____。
(A)电路板上需要钻n个孔，选择一条最短路径使机器移动并完成所有孔的钻孔工作的问题(机器在电路板上钻孔的调度问题)；
(B) n个盘子在三个柱子上的移动问题(梵天塔问题或者说汉诺塔问题)； (C) n座桥， 走过每座桥且仅走过一次的问题(图的遍历问题)； (D)上述(A)(B)(C)都可以。
答案：A 解释：
本题考查对TSP问题抽象的理解
求解TSP问题采用的是贪心算法。(A)选项所描述的问题其实就是TSP问题。（B）选项所描述的问题是梵天塔问题，应该采用的是递归的思想。（C）选项所描述的图的遍历问题，主要有深度优先搜索，和广度优先搜索两种解决方法，不是贪心算法。综上，（A）选项正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(5)关于下列四个数学抽象，说法正确的是_____。
(数学抽象I)城市记为：V={v1,v2,…,vn}，任意两个城市vi,vj∈V之间的距离记为：dvivj，问题的解是寻找所有城市的一个访问顺序T={t1,t2,…,tn}，其中ti∈V，使得min ni=1dtiti+1，这里假定除tn+1=t1外，ti ? tj(i?j时)。
(数学抽象II)电路元件记为：V={v1,v2,…,vn}，任意两个元件vi,vj∈V之间的距离记为：dvivj，问题的解是寻找所有元件之间的一个访问顺序T={t1,t2,…,tn}，其中ti∈V，使得min ni=1dtiti+1，这里假定除tn+1=t1外，ti ? tj(i?j时)。
(数学抽象III)图的结点记为：V={v1,v2,…,vn}，任意两个结点vi,vj∈V的边的权值记为：dvivj，问题的解是寻找所有结点之间的一个访问顺序T={t1,t2,…,tn}，其中ti∈V，使得min ni=1dtiti+1，这里假定除tn+1=t1外，ti ? tj(i?j时)。
(数学抽象IV)图的结点记为：N = {1,2，…，n}，任意两个结点i，j的边的权值记为：dij，问题的解是寻找所有结点之间的一个访问顺序t={t1,t2,…,tn}，其中ti?V，使得min min ni=1dtiti+1，这里假定除tn+1=t1外，ti ? tj(i?j时)。
(A)只有数学抽象I是TSP问题，数学抽象II和III不是；
(B)数学抽象I和III可以被认为是TSP问题，数学抽象II和IV不是； (C)数学抽象I、II、III和IV都可以被认为是TSP问题；