对于本试题的作业处理问题，用图3-25的贪心算法能否求得最高收益? (6)。(能或不能)用贪心算法求解任意给定问题时，是否一定能得到最优解? (7)。(能或不能)
题目
对于本试题的作业处理问题，用图3-25的贪心算法能否求得最高收益? (6)。(能或不能)
用贪心算法求解任意给定问题时，是否一定能得到最优解? (7)。(能或不能)
相似考题
参考答案和解析
正确答案：
这是一道判断贪心算法是否能求得最优解的应用分析题。对于本试题的作业处理问题，用图3-25的贪心算法策略，能求得最优解(即能求得最高收益)。但不是所有的问题都能通过贪心策略来求得最优解，一个典型的例子是0—1背包问题。例如，有3件物品，背包可容纳50磅重的东西，每件物品的详细信息如表3-14所示，问如何装包使得其价值最大?
如果按贪心策略求解该问题，优先选择单位价值最大的物品，则先选择物品R，然后选择物品S。由于此时背包容量还剩下50-10-20=20，不足以容纳物品T，故总价值为60+100=160美元。但若选择物品 S和物品T，容量总和为20+30，小于等于总容量50，得到总价值为100+120=220美元，会得到更优解。此时用贪心策略不能得到最优解。
这是一道判断贪心算法是否能求得最优解的应用分析题。对于本试题的作业处理问题，用图3-25的贪心算法策略，能求得最优解(即能求得最高收益)。但不是所有的问题都能通过贪心策略来求得最优解，一个典型的例子是0—1背包问题。例如，有3件物品，背包可容纳50磅重的东西，每件物品的详细信息如表3-14所示，问如何装包使得其价值最大?
如果按贪心策略求解该问题，优先选择单位价值最大的物品，则先选择物品R，然后选择物品S。由于此时背包容量还剩下50-10-20=20，不足以容纳物品T，故总价值为60+100=160美元。但若选择物品 S和物品T，容量总和为20+30，小于等于总容量50，得到总价值为100+120=220美元，会得到更优解。此时用贪心策略不能得到最优解。
更多“对于本试题的作业处理问题,用图3－25的贪心算法能否求得最高收益?(6)。(能或不能) 用贪心算法求解 ”相关问题
-
第1题：
背包问题可用价值最大贪心策略的贪心算法求得整体最优解。
错误 -
第2题：
关于背包问题，正确的是（)
A．01背包用动态规划求解，部分背包用贪心算法求解
B．01背包用贪心算法求解，部分背包用动态规划求解
C．背包问题都用贪心算法求解
D．背包问题都用动态规划求解
对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题 -
第3题：
2、关于贪心算法，下列叙述中正确的是（）。
A．贪心算法所做出的选择只是在某种意义上的局部最优选择。
B．选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
C．贪心算法并不从整体最优考虑。
D．贪心算法的时间效率最高。
E．贪心算法无法求得问题的最优解。
贪心算法所做出的选择只是在某种意义上的局部最优选择。 -
第4题：
6、问题的 是该问题可以用动态规划算法或贪心算法求解的关键特征
系统可靠性问题;最短路问题;资源分配问题;背包问题 -
第5题：
1、贪心算法在问题求解时，总是做出在当前看来最好的选择，保证可以求得问题的最优解。
错