经典案例解析贪心算法

贪心算法，又名贪婪算法，顾名思义，是指在对问题求解时，总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题，背包最大价值问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

这里我们采用更容易理解的背包最大价值问题：

有一个背包，最多能承载重量为C=150的物品，现在有7个物品（物品不能分割成任意大小），编号为1~7，重量分别是wi=[35,30,60,50,40,10,25]，价值分别是pi=[10,40,30,50,35,40,30]，现在从这7个物品中选择一个或多个装入背包，要求在物品总重量不超过C的前提下，所装入的物品总价值最高。这里需要明确的几个点：1.每个物品都有重量和价值两个属性；2.每个物品分被选中和不被选中两个状态（后面还有个问题，待讨论）；3.可选物品列表已知，背包总的承重量一定。所以，构建描述每个物品的数据体结构OBJECT和背包问题定义为：//typedef是类型定义的意思

//定义待选物体的结构体类型typedefstructtagObject{intweight;intprice;intstatus;}OBJECT;//定义背包问题typedefstructtagKnapsackProblem{vector