贪心算法求解0-1背包问题
贪心算法（又称贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。
No.1 贪心算法的思路
贪心算法一般按如下步骤进行:
①建立数学模型来描述问题。
②把求解的问题分成若干个子问题。
③对每个子问题求解，得到子问题的局部最优解。
④把子问题的解局部最优解合成原来解问题的一个解。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。
背包问题是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
No.2 背包问题的定义
我们有n种物品，物品j的重量为wj，价格为pj。
我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。
如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。
可以用公式表示为:
受限于:
如果限定物品j最多只能选择bj个，则问题称为有界背包问题。
可以用公式表示为:
受限于:
如果不限定每种物品的数量，则问题称为无界背包问题。
各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解。
No.3 背包问题的案例
有旅行者要从n种物品中选取不超过b公斤的物品放入背包，要求总价值最大，设第i种物品的重量为ai，价值为ci(i=1,2,....,n)。定义向量[x1,x2,....,xn]当选第i种物品往背包放时去xi=1，否则取xi=0。
于是所有选取的物品的总价值为:
总的重量为:
问题可描述为:
约束条件为:
贪心算法意为见到好的就抓住不放，用贪心算法求解问题，一般可以获得比较好的求解速度。本问题的具体做法为:先计算物品的价值密度，并把物品按价值密度从大到小的顺序排列：
当选择第ki件物品时，先判断背包是否超载，如果不超载，则放入背包，否则考虑下一件ki+1。按照这种方式考虑所有物品，即能得到背包问题的一个近似最优解。
附录
MATLAB贪心算法解决0-1背包问题 |
function [sch,tolval,tolwei]=backpack(maxwei,weight,value) n=size(weight,2); sch=zeros(1,n); p=value./weight; [a,b]=sort(p);%从小到大排序后的向量，b是对应元素原始下标 b=b(n:-1:1); tw=0;%已装入背包的物品重量 for i=1:n if(tw+weight(b(i)))<=maxwei tw=tw+weight(b(i)); sch(b(i))=1; end end tolwei=tw; tolval=sum(value(find(sch))); |
>> [s,v,t]=backpack(110,[1 10 20 40 45 22 30 55],[10 20 30 50 55 32 40 60])
s =
1 1 1 0 0 1 1 0
v =
132
t =
83 |