求解“背包问题”常用的方法有哪几种?各有什么样的特点?

Question

求解“背包问题”常用的方法有哪几种?各有什么样的特点?

Answer 1

正确答案：“背包问题”求解方法主要是一些启发式算法如贪婪算法、递归算法等。应用递归算法的目的是穷举所有可能的解从中选出最佳解。这种解法实际上是穷举了所有的可能只是加了一些限制。如果所求的数据很大这种算法的效率就不是很高甚至是不可实现的。贪婪法不用穷举且速度快但用贪婪法却不一定能找到最优解。由于贪婪法所得到的解与最优解存在很大的差距当要求较高时就会成为贪婪法致命的且无法挽救的缺陷。
“背包问题”求解方法主要是一些启发式算法，如贪婪算法、递归算法等。应用递归算法的目的是穷举所有可能的解，从中选出最佳解。这种解法实际上是穷举了所有的可能，只是加了一些限制。如果所求的数据很大，这种算法的效率就不是很高，甚至是不可实现的。贪婪法不用穷举且速度快，但用贪婪法却不一定能找到最优解。由于贪婪法所得到的解与最优解存在很大的差距，当要求较高时，就会成为贪婪法致命的且无法挽救的缺陷。 解析：本题考查的是考生对流程图的阅读能力。本题涉及的算法是背包问题。背包问题求解方法很多，考生首先要理解本题中的新方法，然后对照流程图阅读代码。(1)处应该为物品总重量；(2)处应该为物品总价值；(3)处应该为直到达到极限重量limit weight；(4)处应该为继续装物品；(5)处应该为比较当前结果与备份结果。问题2同样是考查有关基本概念的问题。根据软件设计师考试的趋势，本套题设计上有意识地增加了概念考查部分，希望考生能够加强对基本概念的理解与训练。