问题
单项选择题
在下列算法设计方法中, (1) 在求解问题的过程中并不从整体最优上加以考虑,而是做出在当前看来是最好的选择。利用该设计方法可以解决 (2) 问题
2()
A.排序
B.检索
C.背包
D.0-1背包
答案
参考答案:C
解析:
贪心法是这样的一种解题方法:逐步给出解的各部分,在每一步“贪婪地”选择最好的部分解,但不顾及这样选择对整体的影响,因此一般得到的不是最好的解。
解决背包问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。解决背包问题较有效的方法一般用递归和贪婪法,而当背包问题的规模不是很大时,也可采用穷举法。