贪心法求解背包问题例题

背包问题是计算机算法中的经典问题之一。大体上来说，背包问题就是在给定的货物重量、价值和背包最大容量的情况下，如何选择货物使得背包内所装载的货物总价值最大。

贪心法顾名思义，是一种贪婪的算法，其核心思想是：每次选择在当前情况下看起来最优的方案，从而得到全局最优解。那么我们来看一个例子，从多个角度分析如何用贪心法求解背包问题。

例题：

背包容量为 15kg，有 3 种物品分别为：w1=10kg, v1=30元，w2=5kg, v2=20元，w3=2kg, v3=16元。

1. 贪心思路

贪心算法一般有两种思路：

- 按照物品的单位价值从大到小排序取物品

- 按照物品的重量从小到大排序取物品

对于这个例子，我们按照第一种思路来看，计算物品的单位价值，w1的单位价值为 3，w2的单位价值为 4，w3的单位价值为 8。由此我们可以得出排序后的顺序为：w3、w1、w2。

接下来，我们依次将 w3、w1、w2 放入背包，直到背包容量达到 15kg 为止。最终答案为：v3 + v1 + 2/5*v2 = 47.2。

2. 动态规划的结果

动态规划是解决背包问题的一种比较常用的方法。其思路是：对于每个物品，计算在背包容量为 j 时，可获得的最大价值 f(i, j)，其中 i 表示物品编号，j 表示背包容量。而计算 f(i, j) 可以通过之前的计算结果 f(i-1, j)、f(i-1, j-wi) 来实现。

根据动态规划的思路，我们可以列出如下的价值矩阵：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 30 30 30 30 30 30 30 30 30 30 30

2 0 0 0 0 0 30 30 30 30 30 50 50 50 50 50 50

3 0 0 16 16 16 30 30 46 46 46 50 50 66 66 66 66

可以看到，矩阵中最右下角的值为 66，即在背包容量为 15kg 时，能获得的最大价值为 66。

3. 贪心算法与动态规划的比较

通过比较以上两种方法求解背包问题的结果，我们可以得到如下结论：

- 贪心算法所得的结果不是全局最优解，但在大多数情况下，贪心算法所得结果与动态规划所得结果很接近。

- 贪心算法时间复杂度较低，适用于较少物品的情况，而动态规划时间复杂度较高，适用于物品较多的情况。

综上所述，当我们需要求解背包问题时，可以根据具体的情况采用不同的算法。如果物品数量较少，贪心算法有可能得到很接近最优解的结果；而如果物品数量较多，或者需要求解全局最优解，动态规划算法是一个比较好的选择。