贪心算法算是我系统性接触的第一个算法,在学习的过程中页也看了一些书籍和示例,接下来介绍贪心的概念以及一个例子:

  贪心算法主要的思想是局部最优解。贪心算法在目前已有的信息上做出局部最优解,同时做出了选择之后,不管将来有什么结果,选择都不会有所改变,同时,贪心策略的选择对于算法的好坏有着直接的影响。

  贪心算法的特性(满足后可使用):

  1:贪心选择

  指原问题的整体最优解可以通过一系列的局部最优解得出,应用同一规则,将原问题转化为一个相似但规模更小的子问题,而后每一步都是当前最佳的选择。这种选择依赖于已做出的选择。同时,贪心策略无回溯过程。

  2:最优子结构

  当一个问题的最优解包含其子问题的最优解时,称此问题为最优子结构性质。这个性质是该问题能否用贪心解决的关键。

  贪心算法的使用步骤:
  1:制定贪心策略选择一个当前看上去最好的方案(方案的选择尤为重要)。

  2:根据贪心策略一步一步获得局部最优解。

  3:将所有的局部最优解和成为原来问题的一个最优解。

接下来介绍两个示例:

  1:最优装载问题:

  问题描述:有一艘船,载重量为C,有i件古董,重量分别为Wi,如何尽可能多的装载古董?

  解题思路:将古董重量由大到小排序,然后将其依次装入船中,当大于船的重量时停止,最终返回转载的数量。

  题目数据:C:30,W:4,10,7,11,3,5,14,2

  

 1  public int Solution1() {
 2         int C = 30;
 3         int[] W = new int[]{4, 10, 7, 11, 3, 5, 14, 2};
 4         Arrays.sort(W);
 5         int tmp = 0;
 6         int i = 0;
 7         while (tmp <C){
 8             tmp+=W[i];
 9             i++;
10         }
11         return i-1;
12     }//最优装载问题解法

   最后返回值为5,时间复杂度O(n+nlogn)

  2:背包问题:

  问题描述:山中有一个山洞,洞中n种宝物,每种宝物有一定的重量W和价值V,只能运走M重量的宝物,一种拿一样,宝物可分割,如何使宝物价值最大?

  解题思路:选择贪心策略单位价值最大宝物,然后从性价比由高到低选择,最终输出宝物最大价值。

  题目数据:W:4,2,9,5,5,8,5,4,5,5;V:3,8,18,6,8,20,5,6,7,15;M:30

 1 public float Solution2(){
 2         int M=30;
 3         int[] W=new int[]{4,2,9,5,5,8,5,4,5,5};
 4         int[] V=new int[]{3,8,18,6,8,20,5,6,7,15};
 5         Item[] items=new Item[W.length];
 6         for(int i=0;i<W.length;i++){
 7             items[i]=new Item(W[i],V[i]);
 8         }//计算单位重量的价值,并将其存为一个数组
 9         Arrays.sort(items);
10         Item[] item =new Item[items.length];
11         for(int i=0;i<10;i++){
12             item[i]=items[9-i];
13         }//数组翻转
14         float Value=0;
15         int count=0;
16         int tmp=0;//装载的重量
17         while(tmp<M){
18             if(tmp+item[count].getW()>M || tmp+item[count].getW()==M){
19                 break;
20             }else{
21             tmp+=item[count].getW();
22             Value+=item[count].getV();
23             count++;}
24         }
25         int m=M-tmp;//剩下的重量
26         Value+=m*item[count].getV1();//拿走分割后的部分
27         return Value;
28 }
29 public class Item implements Comparable<Item>{
30     private int W;//重量
31     private int V;//价值
32     private float V1;//单位价值
33     public Item(int i1,int i2){
34         this.W=i1;
35         this.V=i2;
36         this.V1=((float) i2)/i1;
37     }
38
39     public float getV1() {
40         return V1;
41     }
42
43     public int getV() {
44         return V;
45     }
46
47     public int getW() {
48         return W;
49     }
50
51     public int compareTo(Item i){
52         if (this.V1>i.getV1()){
53             return 1;
54
55         }else if(this.V1==i.getV1()){
56             return 0;
57         }else if(this.V1<i.getV1()){
58             return -1;
59         }
60         return 0;
61     }
62 }

  最后返回值为70.5,时间复杂度O(n+nlogn)

  在这道题的解题思路中,如果java有c++中的结构体会使后面的代码不那么冗余,在java中需要实现comparable接口实现对象比较,稍微麻烦了些,但总体解题思路是一样的。

12-31 07:57