贪心算法

0-1背包问题

有N个物品，分布具有价值Vi，重量Gi,i= 0,1,2,3....N-1

现在我们的背包最多能承重M，则最多能装多少价值的物品？

贪心策略，每次选择能装的物品中：

(1)、价值最大的

(2)、重量最小的

(3)、单位重量价值最大的

贪心算法的特点与作用：

1、设计简单，计算简便

2、无法保证求得最优解

即使无法求得最优解，也往往能缺德一个不错的可用解

可用于与新开发的算法进行性能对比