贪心算法解析：从单源最短路径到背包问题的求解之道

贪婪算法（又称贪心算法）是指在求解问题时，总是做出当下最优的选择。也就是说，它不考虑整体的最优解，而是做出一定意义上的局部最优解。

贪心算法是一个比较容易理解的算法，以前我也这么认为，感觉贪心就是每一步都达到最优解，但是后来结合问题发现自己的理解有些问题。贪心算法比较经典的一个问题就是单源最短路径问题，这个题的一些步骤我思考了很久，有些细节想不通，以后有机会再讲这个问题，这次讲背包问题。

背包问题就是有若干个物品，每个物品都有自己的价值和重量，背包有总重量，问题就是如何把价值最大的物品装进背包。背包问题有很多种，贪心算法解决的是物品可以拆分的背包问题（也就是物品可以分成几部分装），这个问题用贪心比较容易解决。贪心选择是指通过一系列局部最优的选择，可以得到问题的整体最优解，也就是贪心选择。这是贪心算法可行性的第一个基本要素，也是贪心算法和动态规划算法的主要区别。这个问题就是把每一个条目看成是每一个步骤，解决问题就是把最优解放到每一个步骤里，也就是说，每一个条目里都要放最好的选择。讲到这里，我们就不得不讲到最好的选择。 每次投入的最优选择是每次投入的物品都是剩余物品中价值最大、质量最小的物品。这里要引入一个物品属性，即物品的权重值。物品的权重值是指物品的价值除以物品的质量。所以，这个问题中每次的最优选择是每次选取权重值最大的物品。

既然讨论了问题的大致思路，下面说说具体的算法。算法首先从声明物品类开始，因为后面会用到很多物品属性，用数组会有些麻烦。物品的属性包括背包ID、物品价值、物品品质、物品重量。声明的时候只需要输入物品的前三个属性，通过前三个就可以推导出物品的重量值。算法的下一步就是将物品数组按照物品的重量值进行排序，重量值大的物品放在数组最前面，方便后续计算。算法的主体就是从数组中取出物品对象，计算并比较物品的质量和当前背包剩余重量的大小，如果大，计算要放入的百分比，如果小，为下一步做出最佳选择。算法的大致思路就是这样，下面贴上代码：

 1 package sf;
 2 
 3 import java.util.Scanner;
 4 
 5 public class demo6 
 6 {
 7     //选择排序将数组中的bag按权重排序
 8     public static void sort(Bag[] p)
 9     {
10         Bag t;
11         for(int i=0;i)
12         {
13             int max=i;
14             t=p[i];
15             for(int j=i;j)
16             {
17                 if(t.wi<p[j].wi)
18                 {
19                     t=p[j];
20                     max=j;
21                 }
22             }
23             t=p[i];
24             p[i]=p[max];
25             p[max]=t;
26             
27         }
28     }
29     //背包问题(贪心算法)
30     public static void bq(Bag[] p,int k,int w,double v)
31     {
32         if(p[k].weight<w)
33         {
34             v=v+p[k].value;
35             System.out.println(p[k].pid+"全部装入,当前背包价值为"+v);
36             w=w-p[k].weight;
37             bq(p, k+1, w, v);
38         }else{
39             double a=w*p[k].wi;//当前价值
40             v=v+a;
41             System.out.println(p[k].pid+"装入了"+((double)w/p[k].weight)+",当前背包价值为"+v);
42         }
43         
44     }
45     public static void main(String args[])
46     {
47         System.out.println("请输入背包的容量w和物品的个数n");
48         Scanner reader = new Scanner(System.in);
49         int w=reader.nextInt();//背包的容量
50         int n=reader.nextInt();//物品的个数
51         Bag[] p=new Bag[n];
52         //10 10 a 10 10 b 10 15 c
53         System.out.println("请依次输入各个物品的重量w和价值v和名称s");
54         int weigth;
55         int value;
56         String pid;
57         for(int i=0;i)
58         {
59             weigth=reader.nextInt();
60             value=reader.nextInt();
61             pid=reader.next();
62             p[i]=new Bag(weigth,value,pid);
63         }
64         //System.out.println(z[1]+""+v[1]);
65         sort(p);
66         bq(p,0,w,0.0);
67         for(int i=0;i)
68         {
69             System.out.println(p[i].wi+" "+p[i].pid);
70         }
71         
72     }
73 
74 }
75 
76 class Bag
77 {
78     public int weight;//重量
79     public int value;//价值
80     public double wi;//权重
81     public String pid;//背包名称
82     public  Bag(int w,int v,String pid)
83     {
84         this.weight=w;
85         this.value=v;
86         this.pid=pid;
87         this.wi=(double)value/weight;
88     }
89 }

实现的问题大部分都在注释里，虽然注释不多，但我还是会讲一下。在控制台输入的时候，注意先声明项目，再使用对象属性。一开始一直报错，想了很久，习惯用数组，就直接用数组元素了。排序算法用的是选择，因为选择排序在元素较少的时候计算效果还是比较理想的。贪心算法主体用的是递归，算法实现比较简单，主要就是理解贪心算法的思想，在每一步做出最优解的选择。