?

貪心算法--就是一種尋找局部最優解的情況，然后整合成整體最優解的情況

簡單的例子：買菜的找錢，現在有1元，5角，1角的硬幣，要找給別人2元7角，現在是怎么才能以最少的硬幣量找給別人，肯定是先來兩個1元的，再來1個5角的，最后兩個1角的，但是，這個是我們一眼就能想到的，如何將它抽象成算法的思想呢？

第一步：先找到面值不超過2元7角的最大的硬幣，只有1元，還剩下1元7角

第二步：再找到面值不超過1元7角的最大的硬幣，只有1元，還剩下7角，

第三步，找到面值不超過7角的最大的硬幣，有5角，還剩2角

第四步，找到面值不超過2角的最大的硬幣，有1角，還剩1角

第五步，找到面值不超過1角的最大的硬幣，有1角，還剩0角

第六步，找到面值不超過0角的最大的硬幣，沒有，結束

以上其實就是算法的思想，看似很簡答，其實也是比較繁瑣，最主要的就是找到當前下的最優的解，不管整體怎么樣，思想也很簡單，但是，什么時候去使用貪心算法，這點就很難了，要滿足兩個條件，能夠找到當前的最優的解，其次最優子結構體是整體最優解的一部分，要使用貪心算法之前你得先要驗證是不是可以來使用這個。。。這一點就比較雞肋了，可是，不管怎么來說，最后能不能得到最優解，貪心算法都是執行效率很高的算法思想。

?

說了這么多，實踐才是驗證真理的唯一標準,那我們就來愉快的做個題吧。。。

package thinking;import java.util.ArrayList; import java.util.List; import java.util.Scanner;import org.junit.Test;/* QUESTION : optimal loading problem* DESCRIBTION : Now we have some boxs need to be loaded into a ship which the limit of its load capacity is C ,and* every weight of box is designated by the user. The Volume(體積) of this ship isn't limit. So how can * we load boxes as many as possible? * * */ class Ship{private int capacity;public void setCapacity(int capacity) {this.capacity = capacity;}public int getCapacity() {return capacity;} }class Box{private int weight;public void setWeight(int weight) {this.weight = weight;}public int getWeight() {return weight;} }public class Greedy {Ship ship = new Ship();Box box1 = new Box();Box box2 = new Box();Box box3 = new Box();Box box4 = new Box();Box box5 = new Box();@Testpublic void lookingForTheBestChoise(){// step 1 : initialize the info of ship and boxesSystem.out.println("please input the capacity of ur ship!");Scanner scanner = new Scanner(System.in);int capacity = scanner.nextInt();ship.setCapacity(capacity);System.out.println("please input the werght of ur boxes(5)!");int b1 = scanner.nextInt();int b2 = scanner.nextInt();int b3 = scanner.nextInt();int b4 = scanner.nextInt();int b5 = scanner.nextInt();box1.setWeight(b1);box2.setWeight(b2);box3.setWeight(b3);box4.setWeight(b4);box5.setWeight(b5);List<Box> boxes = new ArrayList<Box>();boxes.add(box1);boxes.add(box2);boxes.add(box3);boxes.add(box4);boxes.add(box5);List<Box> sortedList = sort(boxes);// step 2 : looking for the best solution step by stepint index = 0;while(capacity != 0){if(sortedList.get(0).getWeight() > capacity){System.out.println("ur capacity of ship is too light!");System.exit(0);}else{if(sortedList.get(index).getWeight() < capacity){System.out.print(sortedList.get(index).getWeight());capacity = capacity-sortedList.get(index).getWeight();index++;}else{System.out.println("no more can be loaded");System.exit(0);}}}}List<Box> sort(List<Box> boxes){//List<Box> sortedList = new ArrayList<Box>();for(int i = 0; i<boxes.size(); ++i){for(int j = 0; j < boxes.size()-i-1; ++j){int tempWeight;if(boxes.get(j).getWeight() > boxes.get(j+1).getWeight()){tempWeight = boxes.get(j).getWeight();boxes.get(j).setWeight(boxes.get(j+1).getWeight()); boxes.get(j+1).setWeight(tempWeight);}}}for (Box box : boxes) {System.out.println(box.getWeight());}return boxes;}public static void main(String[] args) {//Scanner s = new Scanner(System.in); } }

上面的問題很簡單，透過現象看本質就是從小到大一個排序的過程，然后累加。。。還不能很好的體現出貪心的這種感覺，那我們就來一個經典一點的背包問題

package thinking;import java.util.Scanner;import org.junit.Test;/* QUESTION : A traveler has a backpack of up to Mkg, and now has n items, each weighing W1, W2,...Wn.The value of* each piece are respectively C1, C2,...,Cn.the number of each item if enough. The maxinum value of a * traveler.* */public class PackageQuestion {int capacity;int n; // 物件的數量 @Testpublic void getMaxValue(){// 輸入物件信息System.out.println("please input the capacity of backpack!");Scanner sca = new Scanner(System.in);capacity = sca.nextInt();System.out.println("please input the number of the items!");n = sca.nextInt();int[] weight = new int[n]; // 重量數組int[] value = new int[n]; // 對應的價值數組int[] index = new int[n]; // 一個額外的記錄變化的數組，后面會進行排序交換，所以每一個物品都要貼一個標簽System.out.println("please input the weight of these items!");for(int i = 0; i<n; ++i){weight[i] = sca.nextInt();}System.out.println("please input the value of these items!");for(int i =0; i<n; ++i){value[i] = sca.nextInt();}//下面就是重場戲了// 因為每個物品的重量和價值都不一樣，直觀可比性不強，所以我們想要一個可以直觀比較的參數，進而想到單位重量下的價值double[] ev = new double[n]; // 單位重量下的價值數組for(int i = 0; i<n; ++i){double v = (double)value[i] / (double)weight[i];ev[i] = v;index[i] = i; //初始化標志 }// 然后下面就是一個復雜的按照價值的由高到低的排序的過程,采用選擇排序或者冒泡都可以。for(int i = 0; i<n-1; ++i){for(int j = i+1; j<n; ++j){if(ev[i] < ev[j]){// 前面的單位重量下的價值小于后面的，就交換位置double temp;temp = ev[i];ev[i] = ev[j];ev[j] = temp;// 位置的改變后，一定要注意標志位置的也要改變int temp3 = index[i];index[i] = index[j];index[j] = temp3;}}}// 用兩個新數組來裝這個排好序的重量和價值int[] wei = new int[n];int[] val = new int[n];for(int i = 0; i<n; ++i){wei[i] = weight[index[i]];val[i] = value[index[i]];}//排好序后的監測一下System.out.println("weight:");for(int i = 0; i<n; ++i){System.out.print(wei[i]+"\t");}System.out.println("value:");for(int i = 0; i<n; ++i){System.out.print(val[i]+"\t");}System.out.println("index:");for(int i = 0; i<n; ++i){System.out.print(index[i]+"\t");}//排好序后就開始進行貪心子結構最優化int x = 0;while(capacity > 0){if(wei[0] > capacity){System.out.println("ur backpack is too small, get changed!");System.exit(0);}else{if(wei[x] < capacity){System.out.println("get the value is "+val[x]+" item");capacity = capacity-wei[x];x++;}else{System.out.println("ur backpack can't pack any more!");System.exit(0);}}}}public static void main(String[] args) {} }

上面這個稍微復雜一些，但還是逃脫不開從最值找的一個步驟，只不過這里的最值稍微做了一點技巧就是求了一個單位最值，從而來提高精準度，并且加上了標志數據的標志，思路也是比較簡單的。

?

轉載于:https://www.cnblogs.com/AmoryWang-JavaSunny/p/6504346.html

總結

以上是生活随笔為你收集整理的Arithmetic_Thinking -- greedy algorithm的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。