小編今天聽到一首超好聽的歌曲，但是百度音樂木有~畢竟要做一個有逼格的IT男，一首《白羊》送給他家~
貪心算法（百度百科）
貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。
貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。
貪心算法（自我理解）
將整體求解拆分成局部求解，在局部中求到最優解，從最大開始出發，從最小開始出發，或者從兩者最出發考慮問題，進而得到局部最優解，再延伸到全局解，但是這個全局解只是相對的，並不一定是最優的解法，但是可以接近最優解，從一個背包問題中就可以看出來：零一背包，部分背包，完全背包。很容易證明，背包問題不能使用貪心算法。但是可以通過動態規劃的方式去解決，這個算法我們日後再看~
[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。 要求儘可能讓裝入背包中的物品總價值最大，但不能超過總容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 價值 10 40 30 50 35 40 30 記得當時學算法的時候，就是這個例子，可以說很經典。 分析： 目標函數： ∑pi最大 約束條件是裝入的物品總重量不超過背包容量，即∑wi<=M( M=150) （1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？ （2）每次挑選所佔重量最小的物品裝入是否能得到最優解？ （3）每次選取單位重量價值最大的物品，成為解本題的策略? 貪心算法是很常見的算法之一，這是由於它簡單易行，構造貪心策略簡單。但是，它需要證明後才能真正運用到題目的算法中。一般來說，貪心算法的證明圍繞著整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。 對於本例題中的3種貪心策略，都無法成立，即無法被證明，解釋如下： （1）貪心策略：選取價值最大者。反例： W=30 物品：A B C 重量：28 12 12 價值：30 20 20 根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。 （2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。 （3）貪心策略：選取單位重量價值最大的物品。反例： W=30 物品：A B C 重量：28 20 10 價值：28 20 10 根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。 值得注意的是，貪心算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的算法。比如，求最小生成樹的Prim算法和Kruskal算法都是漂亮的貪心算法。
小船過河問題
題目:
只有一艘船，能乘2人，船的運行速度為2人中較慢一人的速度，過去後還需一個人把船劃回來，問把n個人運到對岸，最少需要多久。
思路:
先對題目進行分析：一艘船只能一次乘坐兩個人，並且按照兩人中較慢的那個人速度划過去，就比如甲單獨過河只需要1分鐘就過去了，乙單獨過河需要2分鐘，那麼甲和乙一起過河的話就需要2分鐘了（按照最慢的乙的速度），本題看上去有很多的過岸的方式，但題目中說到了最少需要的時間，這時候就要從最優去分析了，這是立馬想到的就是貪心算法：要麼從最快開始分解，要麼從最慢開始分解，顯然本題從最慢的開始著手去考慮，因為船速是按照兩人中較慢那個人的速度，那麼最慢和較慢的兩個兩個人成了我們解題的關鍵，如何把最慢和第二慢的這兩個人送到河的對岸成為了最核心的問題，送完之後，再送第三慢和第四慢的，以此類推，這就是貪心算法的核心思想了，小夥伴們會想到很多的過岸的方式，但從最快時間考慮，
小夥伴們首先想到的就是這種方法：
1.讓最快的和最慢的乘船過河，然後最快的乘船回來，再讓最快的和第二慢的一同乘船過河，之後最快的乘船回來（再去接更多的人~）這是最常想到的方法，也是解法相對最優的情況，花費時間2*time[0]+time[n-2]+time[n-1](下標從0開始，所以數組中n-1代表第n個）
還有一種方法也是最優解的有力競爭~
2.先讓最快的和較快的乘船過去，接著最快的乘船回來，再讓最慢的和第二慢的乘船過去，較快的乘船回來，這是第二種方式（從情理上來講相對合理，因為第一種的話最快的太累了，哈哈）這種方法花費的時間time[0]+2*time[1]+time[n-1]
除了以上兩種情況，小夥伴們可以考慮一下，其他的方式花費的時間更多（實際上如果這些人之間速度相差很多選第二種較快，如果速度相差很小，就要根據具體的數據進行分析了~）
還可以用到前面學到的遞歸算法進行解題~有興趣的小夥伴可以自己嘗試一下哦~
下面是原始碼：
package 貪心算法;import java.util.Arrays;import java.util.Scanner;public class 小船過河 {public static void main(String[] args) { int sum=0; Scanner sc = new Scanner(System.in); //t為共有多少組過河的人 //int t=sc.nextInt(); //for(int i=t;i>0;i--){ //n為要過河的人數 int n=sc.nextInt(); int a[]=new int[n]; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); } sc.close(); //對數組a進行升序排列 Arrays.sort(a);//java自帶的排序函數，自己也可以實現。 //實現循環，每次把最慢的和較慢的人送過去，因此每次減去2 while(n>3){ //Math包自帶的判斷大小的函數，可直接使用，也可以寫一個單獨的函數實現 sum=Math.min(sum+a[0]+2*a[1]+a[n-1], sum+2*a[0]+a[n-1]+a[n-2]); n-=2; } System.out.println(sum); //如果是三個人直接把三個人的時間加起來就可以了~ if(n==3){ sum+=a[0]+a[1]+a[2]; } //如果是兩個人，時間直接是較慢的人的。 else if(n==2){ sum+=a[1]; } //一個人的話，時間就是他本身~ else{ sum+=a[0]; } System.out.println(sum); //} }}
結語：
成功的路上並不擁擠，因為懂得堅持的人不多。
我是愛編程的小蘿蔔頭，我為編程代言~