“365算法每日學計劃”：03打卡-貪心算法

cdn.xitu.io/2018/6/16/16408e765b10952e?w=800&h=444&f=jpeg&s=52647">

自從開始做公眾號開始，就一直在思考，怎么把算法的訓練做好，因為思海同學在算法這方面的掌握確實還不夠。因此，我現在想做一個“365算法每日學計劃”。

“計劃”的主要目的：

1、想通過這樣的方式監督自己更努力的學習算法。

2、想和小伙伴們“組團”一起來學習交流學習算法過程中的點點滴滴。 “

計劃”的主要內容：

1、數據結構和算法的基礎知識鞏固。

2、逐步進階的oj算法訓練。 “計劃”的時間安排：每周三和周六 文章有點長，希望能耐心的看完。

——說在前面

“算法每日學”計劃01打卡:

問題描述

已知一個正整數N，問從1~N中任選出三個數，他們的最小公倍數最大可以為多少。 輸入格式

輸入一個正整數N。 輸出格式 輸出一個整數，表示你找到的最小公倍數。 樣例輸入 9 樣例輸出 504 數據規模與約定

1 <= N <= 106。

解題思路與實現

下面這個思路是“算法每日學交流社區”的小伙伴給出的，感謝小伙伴們的支持與關注。

思路分析：

最大 最小公倍數，聯想到兩個數的求最大最小公倍數，即兩個數的乘積（注：連續的兩個自然數是互斥的）。

同樣，我們可以拿最后三個數來做考慮。

1.當n為奇數時，n，n-1，n-2為奇偶奇，里面只有一個偶數，所以不會有2這個因子。這三個數相差不到3，所以也不會有因子3，故符合題意。

2.當n為偶數時，n，n-1，n-2為偶奇偶，此時n，n-2肯定含有因子2，所以除于2不值得。所以考慮將n-2 換成n-3，變成奇偶奇，此時也有一個問題，

n和n-3，如果n%3==0，則除于3更不值得。仍根據奇偶奇的原則，變動偶數n為n-2，此時換成n-1，n-2，n-3和1情況一樣。故此時符合題意。

所以根據上面的分析，我們可以寫出下面的代碼：

 1import java.util.Scanner;
 2public class Main{
 3    public static void main(String[] args) {
 4        Scanner scanner = new Scanner(System.in);
 5        long n = scanner.nextLong(); 
 6        long result;
 7        if(n<3)  
 8            result=n;  
 9        else{  
10        if(n%2!=0)  
11            result=n*(n-1)*(n-2);  
12        else if(n%3!=0)  
13            result=n*(n-1)*(n-3);  
14        else  
15            result=(n-1)*(n-2)*(n-3);  
16        }  
17        System.out.println(result);
18    }
19}

其實，上面的算法是用到了貪心的思想，大概是這樣的思路：

從最大的三個數開始考慮，如果最大的數為奇數，那么相鄰的三個數中有兩個奇數，最大公約數為1，最小公倍數就為n(n-1)(n-2).   如果為偶數，那么往后移，考慮n(n-1)(n-3),這時n和n-3相差3，式子滿足條件的前提是n不能被3整除，否則結果只能是(n-1)(n-2)(n-3).

這個題目因為用到了貪心的思想，所以下面介紹一下貪心算法。

貪心算法

一、基本概念：

所謂貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。

貪心算法沒有固定的算法框架，算法設計的關鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優解，選擇的貪心策略必須具備無后效性，即某個狀態以后的過程不會影響以前的狀態，只與當前狀態有關。

所以對所采用的貪心策略一定要仔細分析其是否滿足無后效性。

二、貪心算法的基本思路：

1.建立數學模型來描述問題。 2.把求解的問題分成若干個子問題。 3.對每一子問題求解，得到子問題的局部最優解。 4.把子問題的解局部最優解合成原來解問題的一個解。

三、貪心算法適用的問題

貪心策略適用的前提是：局部最優策略能導致產生全局最優解。

實際上，貪心算法適用的情況很少。一般，對一個問題分析是否適用于貪心算法，可以先選擇該問題下的幾個實際數據進行分析，就可做出判斷。

四、貪心算法的實現框架

1 從問題的某一初始解出發；
2 while （能朝給定總目標前進一步）
3  { 
4        利用可行的決策，求出可行解的一個解元素；
5  }
6  由所有解元素組合成問題的一個可行解；

五、貪心策略的選擇

因為用貪心算法只能通過解局部最優解的策略來達到全局最優解，因此，一定要注意判斷問題是否適合采用貪心算法策略，找到的解是否一定是問題的最優解。

六、例題分析

下面是一個可以試用貪心算法解的題目，貪心解的確不錯，可惜不是最優解。

例題① [背包問題] 有一個背包，背包容量是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，則答案錯誤。

例題②［均分紙牌］有N堆紙牌，編號分別為1，2，…，n。每堆上有若干張,但紙牌總數必為n的倍數.可以在任一堆上取若干張紙牌,然后移動。移牌的規則為：在編號為1上取的紙牌，只能移到編號為2的堆上；在編號為n的堆上取的紙牌，只能移到編號為n-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。現在要求找出一種移動方法，用最少的移動次數使每堆上紙牌數都一樣多。例如：n=4，4堆紙牌分別為：①  9 ② 8 ③ 17 ④ 6 移動三次可以達到目的：從③取4張牌放到④ 再從③區3張放到②然后從②去1張放到①。

輸入輸出樣例：4

9 8 17 6

屏幕顯示：3

算法分析：設a[i]為第I堆紙牌的張數（0<=I<=n），v為均分后每堆紙牌的張數，s為最小移動次數。

我們用貪心算法，按照從左到右的順序移動紙牌。如第I堆的紙牌數不等于平均值，則移動一次（即s加1），分兩種情況移動：

1．若a[i]>v，則將a[i]-v張從第I堆移動到第I+1堆； 2．若a[i]<v，則將v-a[i]張從第I+1堆移動到第I堆。

為了設計的方便，我們把這兩種情況統一看作是將a[i]-v從第I堆移動到第I+1堆，移動后有a[i]=v; a[I+1]=a[I+1]+a[i]-v.

在從第I+1堆取出紙牌補充第I堆的過程中可能回出現第I+1堆的紙牌小于零的情況。

如n=3，三堆指派數為1 2 27 ，這時v=10，為了使第一堆為10，要從第二堆移9張到第一堆，而第二堆只有2張可以移，這是不是意味著剛才使用貪心法是錯誤的呢？

我們繼續按規則分析移牌過程，從第二堆移出9張到第一堆后，第一堆有10張，第二堆剩下-7張，在從第三堆移動17張到第二堆，剛好三堆紙牌都是10，最后結果是對的，我們在移動過程中，只是改變了移動的順序，而移動次數不便，因此此題使用貪心法可行的。

Java源程序

 1public class Greedy {
 2    public static void main(String[] args) {
 3        int n = 0, avg = 0, s = 0;
 4        Scanner scanner = new Scanner(System.in);
 5        ArrayList<Integer> array = new ArrayList<Integer>();
 6        System.out.println("Please input the number of heaps:");
 7        n = scanner.nextInt();
 8        System.out.println("Please input heap number:");
 9        for (int i = 0; i < n; i++) {
10            array.add(scanner.nextInt());
11        }
12        for (int i = 0; i < array.size(); i++) {
13            avg += array.get(i);
14        }
15        avg = avg / array.size();
16        System.out.println(array.size());
17        System.out.println(avg);
18        for (int i = 0; i < array.size() - 1; i++) {
19            s++;
20            array.set(i + 1, array.get(i + 1) + array.get(i) - avg);
21        }
22        System.out.println("s:" + s);
23    }
24}

利用貪心算法解題，需要解決兩個問題：

一是問題是否適合用貪心法求解。我們看一個找幣的例子，如果一個貨幣系統有三種幣值，面值分別為一角、五分和一分，求最小找幣數時，可以用貪心法求解；如果將這三種幣值改為一角一分、五分和一分，就不能使用貪心法求解。用貪心法解題很方便，但它的適用范圍很小，判斷一個問題是否適合用貪心法求解，目前還沒有一個通用的方法，在信息學競賽中，需要憑個人的經驗來判斷。

二是確定了可以用貪心算法之后，如何選擇一個貪心標準，才能保證得到問題的最優解。在選擇貪心標準時，我們要對所選的貪心標準進行驗證才能使用，不要被表面上看似正確的貪心標準所迷惑，如下面的例子。

例題③［最大整數］設有n個正整數，將它們連接成一排，組成一個最大的多位整數。

例如：n=3時，3個整數13，312，343，連成的最大整數為34331213。

又如：n=4時，4個整數7，13，4，246，連成的最大整數為7424613。

輸入：n N個數 輸出：連成的多位數

算法分析：此題很容易想到使用貪心法，在考試時有很多同學把整數按從大到小的順序連接起來，測試題目的例子也都符合，但最后測試的結果卻不全對。按這種標準，我們很容易找到反例：12，121應該組成12121而非12112，那么是不是相互包含的時候就從小到大呢？也不一定，如12，123就是12312而非12123，這種情況就有很多種了。是不是此題不能用貪心法呢？

其實此題可以用貪心法來求解，只是剛才的標準不對，正確的標準是：先把整數轉換成字符串，然后在比較a+b和b+a，如果a+b>=b+a，就把a排在b的前面，反之則把a排在b的后面。

java源程序

 1public static void main(String[] args) {
 2        String str = "";
 3        ArrayList<String> array = new ArrayList<String>();
 4        Scanner in = new Scanner(System.in);
 5        System.out.println("Please input the number of data:");
 6        int n = in.nextInt();
 7        System.out.println("Please input the data:");
 8        while (n-- > 0) {
 9            array.add(in.next());
10        }
11        for (int i = 0; i < array.size(); i++)
12            for (int j = i + 1; j < array.size(); j++) {
13                if ((array.get(i) + array.get(j)).compareTo(array.get(j) + array.get(i)) < 0) {
14                    String temp = array.get(i);
15                    array.set(i, array.get(j));
16                    array.set(j, temp);
17                }
18            }
19        for (int i = 0; i < array.size(); i++) {
20            str += array.get(i);
21        }
22        System.out.println("str=:" + str);
23    }
24}

貪心算法所作的選擇可以依賴于以往所作過的選擇，但決不依賴于將來的選擇，也不依賴于子問題的解，因此貪心算法與其他算法相比具有一定的速度優勢。如果一個問題可以同時用幾種方法解決，貪心算法應該是最好的選擇之一。

這就是貪心的一些思想和基本的應用了，如果還有什么問題，可以留言或者私信我！

參考資料

• https://blog.csdn.net/a925907195/article/details/41314549

往期推薦

• “面試不敗計劃”： java語言基礎面試題（二）

• ”365算法每日學計劃”：02打卡-線性表（贈書活動第①期預告）

• 并發基礎篇（一）： 線程介紹