【贪心算法】背包问题–可分割

【问题描述】

给定一个载重量为M的背包，考虑n个物品，其中第i个物品的重量 ，价值wi （1≤i≤n），要求把物品装满背包，且使背包内的物品价值最大。

有两类背包问题（根据物品是否可以分割），如果物品不可以分割，称为0—1背包问题（动态规划）；如果物品可以分割，则称为背包问题（贪心算法）。

【算法分析】
假设背包的容量为50，有3个物品：
有3种方法来选取物品： （1）当作0—1背包问题，用动态规划算法，获得最优值220； （2）当作0—1背包问题，用贪心算法，按性价比从高到底顺序选取物品，获得最优值160。由于物品不可分割，剩下的空间白白浪费。 （3）当作背包问题，用贪心算法，按性价比从高到底的顺序选取物品，获得最优值240。由于物品可以分割，剩下的空间装入物品3的一部分，而获得了更好的性能。
【算法分析】
数据结构：
struct bag{
int w; //物

【贪心算法】背包问题–可分割最先出现在Python成神之路。