贪心算法 - 0-1背包问题(转载)

贪心算法——0-1背包问题

0/1 背包问题
有一个容量为weight的背包，现在要从n件物品中选取若干件装入背包中，每件物品i的重量为w[i]，
价值为p[i]。定义一种可行的背包装载为：背包中物品的总重不能超过背包的容量，并且一件物品要么全部选取，要么不选取。定义最佳装载是指所装入的物品价值最高，并且是可行的背包装载。

【样例输入】
11 {weight}
4 {n}
2 4 6 7 {w[i]}
6 10 12 13 {p[i]}

【样例输出】
0 1 0 1
23

【问题分析】
设有数组chosen[1..n]，若chosen[i]=1，表示物品i被装入了背包中，chosen[i]=0表示物品i不
装入背包中。那么，chosen[0,1,0,1]就是一种可行的背包装载方案，也是一种最佳的装载方案，此时的总价值为23。

【算法分析】
0/1背包问题有好几种贪心策略，每种贪心策略都是采用多步过程来完成背包的装入，在每一步中，
都是利用某种固定的贪心准则来选择将某一件物品装入背包。

一种贪心准则为：从剩余的物品中，选出可以装入背包的价值最大的物品。这种贪心准则不能保证得
到最优解。例如，weight=105，n=3，w=[100,10,10]，p=[20,15,15]，按照以上这种“价值贪心准则”，获得的解为choice=[1,0,0]，这种方案的总价值为20，而最优解为choice=[0,1,1]，其总价值为30。

另一种方案是“重量贪心准则”，即从剩下的物品中，选择可以装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下，不一定能得到最优解，例如，weight=25，n=2，
w=[10,20]，p=[5,100]。获得的解为choice=[1,0]，总价值为5，比最优解choice=[0,1]的总价值100要差。

本题还有一种方案，即“单位价值贪心准则”，这种方案是从剩余物品中，选择可装入包的p[i]/w[i]
值最大的物品，这种策略也不能保证得到最优解。例如，weight=30，n=3，w=[20,15,15]，p=[40,25,25]。
获得的解为choice=[1,0,0]，总价值为40，而最优解为choice=[0,1,1]的总价值为50。
其实，0/1背包问题是一个复杂的NP问题。对于这类问题，也许根本就不存在多项式时间的算法。在
用贪心法解这类问题时，我们还可以结合其他的一些优化策略，如启发式策略等，使解的结果与最优解相差在一定的范围内，也就是，可以得到原问题的近似最优解。另外，在解本题这样的问题时，还可以采用动态规划方法。

 

 

转自: http://liuyangxdgs.blog.163.com/blog/static/29137763200851405846156/