直观上能感觉是可以用贪心算法解背包问题，但要证明是否具有贪心选择性质，我也不知道该如何说明才准确，毕竟证明是一个严谨的问题。
不过我可以说明从贪心算法和动态规划中，为何要选用贪心算法做出解释。
首先，问题具有最优子结构性质，那么可用的算法也就动态规划算法和贪心算法，它们都要求具有最优子结构性质，好像就这两种算法吧。
接着，动态规划算法都要求建立递归关系式，因为它的每一个当前解都是从子问题的最优解综合的出来的。而贪心算法不需要建立递归式，它是将原问题逐层分解，它需要的是建立贪心选择策略。
背包问题无法建立递归式，能建立贪心选择策略，所以，背包问题选择贪心算法做。
不明白
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024