2. 计算机
  3. 根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。 求解“背包问题”常用的方法有哪几种?各有什么样的特点?

根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。 求解“背包问题”常用的方法有哪几种?各有什么样的特点?

admin2009-02-15  90
问题 根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。
求解“背包问题”常用的方法有哪几种?各有什么样的特点?
选项
答案“背包问题”求解方法主要是一些启发式算法，如贪婪算法、递归算法等。应用递归算法的目的是穷举所有可能的解，从中选出最佳解。这种解法实际上是穷举了所有的可能，只是加了一些限制。如果所求的数据很大，这种算法的效率就不是很高，甚至是不可实现的。贪婪法不用穷举且速度快，但用贪婪法却不一定能找到最优解。由于贪婪法所得到的解与最优解存在很大的差距，当要求较高时，就会成为贪婪法致命的且无法挽救的缺陷。
解析 本题考查的是考生对流程图的阅读能力。本题涉及的算法是背包问题。背包问题求解方法很多，考生首先要理解本题中的新方法，然后对照流程图阅读代码。(1)处应该为物品总重量；(2)处应该为物品总价值；(3)处应该为直到达到极限重量limit weight；(4)处应该为继续装物品；(5)处应该为比较当前结果与备份结果。问题2同样是考查有关基本概念的问题。根据软件设计师考试的趋势，本套题设计上有意识地增加了概念考查部分，希望考生能够加强对基本概念的理解与训练。
转载请注明原文地址:https://kaotiyun.com/show/SgDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)