贪心背包，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。(Greedy knapsack, (1) the so-called greedy choice property means that the overall optimal solution of the problem can be achieved through a series of local optimal solutions, namely greedy selection. This is the first essential element of the greedy algorithm, and it is also the main difference between the greedy algorithm and the dynamic programming algorithm.


(2) when the optimal solution of a problem contains the optimal solution of its subproblem, it is called the optimal substructure property. The optimal substructure of the problem is the key feature of the problem which can be solved by the dynamic programming algorithm or the greedy algorithm.)