“365算法每日學(xué)計(jì)劃”：03打卡-貪心算法

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

自從開始做公眾號開始，就一直在思考，怎么把算法的訓(xùn)練做好，因?yàn)樗己Ｍ瑢W(xué)在算法這方面的掌握確實(shí)還不夠。因此，我現(xiàn)在想做一個(gè)“365算法每日學(xué)計(jì)劃”。

“計(jì)劃”的主要目的：

1、想通過這樣的方式監(jiān)督自己更努力的學(xué)習(xí)算法。

2、想和小伙伴們“組團(tuán)”一起來學(xué)習(xí)交流學(xué)習(xí)算法過程中的點(diǎn)點(diǎn)滴滴。 “

計(jì)劃”的主要內(nèi)容：

1、數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)知識鞏固。

2、逐步進(jìn)階的oj算法訓(xùn)練。 “計(jì)劃”的時(shí)間安排：每周三和周六 文章有點(diǎn)長，希望能耐心的看完。

——說在前面

“算法每日學(xué)”計(jì)劃01打卡:

問題描述

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

輸入一個(gè)正整數(shù)N。 輸出格式 輸出一個(gè)整數(shù)，表示你找到的最小公倍數(shù)。 樣例輸入 9 樣例輸出 504 數(shù)據(jù)規(guī)模與約定

1 <= N <= 106。

解題思路與實(shí)現(xiàn)

下面這個(gè)思路是“算法每日學(xué)交流社區(qū)”的小伙伴給出的，感謝小伙伴們的支持與關(guān)注。

思路分析：

最大 最小公倍數(shù)，聯(lián)想到兩個(gè)數(shù)的求最大最小公倍數(shù)，即兩個(gè)數(shù)的乘積（注：連續(xù)的兩個(gè)自然數(shù)是互斥的）。

同樣，我們可以拿最后三個(gè)數(shù)來做考慮。

1.當(dāng)n為奇數(shù)時(shí)，n，n-1，n-2為奇偶奇，里面只有一個(gè)偶數(shù)，所以不會(huì)有2這個(gè)因子。這三個(gè)數(shù)相差不到3，所以也不會(huì)有因子3，故符合題意。

2.當(dāng)n為偶數(shù)時(shí)，n，n-1，n-2為偶奇偶，此時(shí)n，n-2肯定含有因子2，所以除于2不值得。所以考慮將n-2 換成n-3，變成奇偶奇，此時(shí)也有一個(gè)問題，

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

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

 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}

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

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

這個(gè)題目因?yàn)橛玫搅素澬牡乃枷?，所以下面介紹一下貪心算法。

貪心算法

一、基本概念：

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

貪心算法沒有固定的算法框架，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性，即某個(gè)狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

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

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

1.建立數(shù)學(xué)模型來描述問題。 2.把求解的問題分成若干個(gè)子問題。 3.對每一子問題求解，得到子問題的局部最優(yōu)解。 4.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。

三、貪心算法適用的問題

貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解。

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

四、貪心算法的實(shí)現(xiàn)框架

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

五、貪心策略的選擇

因?yàn)橛秘澬乃惴ㄖ荒芡ㄟ^解局部最優(yōu)解的策略來達(dá)到全局最優(yōu)解，因此，一定要注意判斷問題是否適合采用貪心算法策略，找到的解是否一定是問題的最優(yōu)解。

六、例題分析

下面是一個(gè)可以試用貪心算法解的題目，貪心解的確不錯(cuò)，可惜不是最優(yōu)解。

例題① [背包問題] 有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品可以分割成任意大小。 要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過總?cè)萘俊?物品 A B C D E F G 重量 35 30 60 50 40 10 25 價(jià)值 10 40 30 50 35 40 30

分析：目標(biāo)函數(shù)： ∑pi最大約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)（1）根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？ （2）每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？ （3）每次選取單位重量價(jià)值最大的物品，成為解本題的策略。

值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經(jīng)過證明成立后，它就是一種高效的算法。 貪心算法還是很常見的算法之一，這是由于它簡單易行，構(gòu)造貪心策略不是很困難。

可惜的是，它需要證明后才能真正運(yùn)用到題目的算法中。

一般來說，貪心算法的證明圍繞著：整個(gè)問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的。 對于例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：

（1）貪心策略：選取價(jià)值最大者。反例：

W=30 物品：A B C 重量：28 12 12 價(jià)值：30 20 20

根據(jù)策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。

（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。 （3）貪心策略：選取單位重量價(jià)值最大的物品。反例：

W=30 物品：A B C 重量：28 20 10 價(jià)值：28 20 10

根據(jù)策略，三種物品單位重量價(jià)值一樣，程序無法依據(jù)現(xiàn)有策略作出判斷，如果選擇A，則答案錯(cuò)誤。

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

輸入輸出樣例：4

9 8 17 6

屏幕顯示：3

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

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

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

為了設(shè)計(jì)的方便，我們把這兩種情況統(tǒng)一看作是將a[i]-v從第I堆移動(dòng)到第I+1堆，移動(dòng)后有a[i]=v; a[I+1]=a[I+1]+a[i]-v.

在從第I+1堆取出紙牌補(bǔ)充第I堆的過程中可能回出現(xiàn)第I+1堆的紙牌小于零的情況。

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

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

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}

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

一是問題是否適合用貪心法求解。我們看一個(gè)找?guī)诺睦?，如果一個(gè)貨幣系統(tǒng)有三種幣值，面值分別為一角、五分和一分，求最小找?guī)艛?shù)時(shí)，可以用貪心法求解；如果將這三種幣值改為一角一分、五分和一分，就不能使用貪心法求解。用貪心法解題很方便，但它的適用范圍很小，判斷一個(gè)問題是否適合用貪心法求解，目前還沒有一個(gè)通用的方法，在信息學(xué)競賽中，需要憑個(gè)人的經(jīng)驗(yàn)來判斷。

二是確定了可以用貪心算法之后，如何選擇一個(gè)貪心標(biāo)準(zhǔn)，才能保證得到問題的最優(yōu)解。在選擇貪心標(biāo)準(zhǔn)時(shí)，我們要對所選的貪心標(biāo)準(zhǔn)進(jìn)行驗(yàn)證才能使用，不要被表面上看似正確的貪心標(biāo)準(zhǔn)所迷惑，如下面的例子。

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

例如：n=3時(shí)，3個(gè)整數(shù)13，312，343，連成的最大整數(shù)為34331213。

又如：n=4時(shí)，4個(gè)整數(shù)7，13，4，246，連成的最大整數(shù)為7424613。

輸入：n N個(gè)數(shù) 輸出：連成的多位數(shù)

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

其實(shí)此題可以用貪心法來求解，只是剛才的標(biāo)準(zhǔn)不對，正確的標(biāo)準(zhǔn)是：先把整數(shù)轉(zhuǎn)換成字符串，然后在比較a+b和b+a，如果a+b>=b+a，就把a(bǔ)排在b的前面，反之則把a(bǔ)排在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}

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

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

參考資料

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

往期推薦

• “面試不敗計(jì)劃”： java語言基礎(chǔ)面試題（二）

• ”365算法每日學(xué)計(jì)劃”：02打卡-線性表（贈(zèng)書活動(dòng)第①期預(yù)告）

• 并發(fā)基礎(chǔ)篇（一）： 線程介紹