背包问题(上) | 贪心算法与MATLAB程序实现
Building可视库
一起做些更酷的事吧！
关注
看到这篇推文的时候，说明小库又去上了《优化与决策》这门课，今晚老师讲的是动态规划问题，涉及最短路径问题，库存问题，资源分配，生产过程最优化问题等等。
不过我们这次的重点是在书上有个例题提到了背包问题，以及例题中的这句话：应用贪心算法，可以很好而快速的解决。按耐不住，开始探索~
背包问题
所谓背包问题，用知乎某答主的话讲就是：一个小偷背了一个背包潜进了金店，包就那么大，他如何保证他背出来所有物品加起来的价值最大。
当然背包问题分为好几种：0/1背包问题，完全背包问题，多重背包问题。今天咱们就只说第一种，也是最基础的。
问题描述
已知6种物品和一个可载重量为60千克的背包，物品i的重量为a，价值为c，在装包时每一件物品可以装入，也可以不装，假定背包的容积够大（但可载质量有限），我们如何确定装包，使所装包的总价值最大？
求解思路
第一：这里需要定义决策向量：
[x1,x2,x3,x4,x5,x6]
即当选择第i种物品往背包放时，取xi=1，否则取xi=0。于是所有选取的物品的总价值为：
c1x1+c2x2+…+Cnxn
总的重量为：
a1x1+a2x2+…+anxn
可以表达为：
第二：贪心算法意为见到好的就抓住不放，用贪心算法求解问题，一般可以获得比较好的求解速度。本问题的具体做法为：先计算物品的价值密度，并把物品按价值密度从大到小的顺序排列：
第三：当选择第ki件已排好序的物品时，先判断背包是否超载，如果不超载，则物品放入背包，否则考虑下一件k(i+1)，按照这种方式考虑所有物品，即能得到背包问题的一个近似最优解。
程序求解
贪心算法脚本文件代码如下：
问题结果如下：
其中决策序列s符合课本所示(0,1,1,1,1,0),该策略所得总效益为130，总载量为58kg。
需要说明的是贪心算法得到只是近似最优解，对于这个例题，最优解序列应为(0,1,1,0,1,1)，总效益应为134，总载量为60kg，下次用动态规划去求解此类问题的最优解。
图文 | 小库Q
编辑 | Jason