藍(lán)橋杯上岸每日N題 第七期(小貓爬山)！?。?/h2>

同步收錄 ??

藍(lán)橋杯上岸必背?。?！(第四期DFS)

大家好 我是寸鐵??

沖刺藍(lán)橋杯省一模板大全來啦 ??

藍(lán)橋杯4月8號(hào)就要開始了 ??

距離藍(lán)橋杯省賽倒數(shù)第3天 ?? ?? ??

還沒背熟模板的伙伴們背起來 ?? ?? ??

真題千千萬萬遍，藍(lán)橋省一自然現(xiàn)！ ??

日更3000里，藍(lán)橋眷顧你 ??

暴力出奇跡，打表過樣例 ??

祝大家4月8號(hào)藍(lán)橋杯上岸 ??

不清楚藍(lán)橋杯考什么的點(diǎn)點(diǎn)下方??

考點(diǎn)秘籍

想背純享模版的伙伴們點(diǎn)點(diǎn)下方??

藍(lán)橋杯省一你一定不能錯(cuò)過的模板大全(第一期)

藍(lán)橋杯省一你一定不能錯(cuò)過的模板大全（第二期）

藍(lán)橋杯省一你一定不能錯(cuò)過的模板大全（第三期）

藍(lán)橋杯省一你一定不能錯(cuò)過的模板大全（第四期）?。?！

想背注釋模版的伙伴們點(diǎn)點(diǎn)下方??

藍(lán)橋杯必背第一期

藍(lán)橋杯必背第二期

往期精彩回顧

藍(lán)橋杯上岸每日N題 第一期(一)?。?！

藍(lán)橋杯上岸每日N題第一期(二)！?。?/h3>

藍(lán)橋杯上岸每日N題第一期(三)?。?！

藍(lán)橋杯上岸每日N題第二期(一)?。?！

藍(lán)橋杯上岸每日N題第三期(一)！?。?/h3>

藍(lán)橋杯上岸每日N題 第四期(最少刷題數(shù))?。?！

藍(lán)橋杯上岸每日N題 第五期(山)！?。?/h3>

藍(lán)橋杯上岸每日N題 第六期(求階乘)?。?！

操作系統(tǒng)期末題庫 第九期(完結(jié))

LeetCode Hot100 刷題(第三期)

idea創(chuàng)建SpringBoot項(xiàng)目報(bào)錯(cuò)解決方案

數(shù)據(jù)庫SQL語句（期末沖刺）

想看JavaB組填空題的伙伴們點(diǎn)點(diǎn)下方 ??

填空題

競(jìng)賽干貨

算法競(jìng)賽字符串常用操作大全

藍(lán)橋杯上岸必刷?。?！(模擬/枚舉專題)

藍(lán)橋杯上岸必背?。?！ (第三期 DP)

藍(lán)橋杯上岸必背?。?！(第四期DFS)

藍(lán)橋杯上岸必背?。?！(第五期BFS)

藍(lán)橋杯上岸必背?。?！(第六期樹與圖的遍歷)

藍(lán)橋杯上岸必背！??！(第七期 最短路算法)

藍(lán)橋杯上岸必背?。。?第八期 簡(jiǎn)單數(shù)論)

喜歡的小伙伴可以關(guān)注我，關(guān)注寸鐵，我們一起上岸4.8藍(lán)橋杯?。?！

小貓爬山

考點(diǎn)：DFS+可行性剪枝

分析

要盡可能減少花費(fèi)-->遞歸的分支盡可能少-->優(yōu)先考慮放重貓
優(yōu)先考慮放重貓，需要從大到小排個(gè)序，
一直往下搜索，答案是唯一的。
放得下貓就繼續(xù)往該車往下加
放不下就再另外開一輛放貓
分兩個(gè)分支去放
開一輛繼續(xù)放其他貓的為一個(gè)分支
開另一輛單獨(dú)只放一只貓的為另一個(gè)分支
接下來遞歸調(diào)用處理，對(duì)于每個(gè)分支遞歸后有又n個(gè)分支，一直遞歸下去，直至遞歸到n層。說明當(dāng)前的車數(shù)為最優(yōu)解。
我們可以建立如下遞歸搜索圖：

DFS小結(jié)：

遞歸DFS最簡(jiǎn)單直接的理解方式就是按照你的做題邏輯順序來寫
所以做題的邏輯順序至關(guān)重要，確保不重不漏地確保方案。
邏輯正確跑出來答案正確即可，不要過分地去深究?jī)?nèi)在實(shí)現(xiàn)，會(huì)很糾結(jié)。
注意dfs下一層要恢復(fù)現(xiàn)場(chǎng)，這是必需的。
深究不外乎：遞歸下一層+置false回溯上一層用+去掉無用的分支剪枝

Accode

//從大到小排個(gè)序，優(yōu)先放重貓。
//一直往下搜索，答案是唯一的。
//放得下貓就繼續(xù)往下加
//放不下就再另外開一輛，繼續(xù)放
//分兩個(gè)分支去放
//開一輛繼續(xù)放其他貓的有一個(gè)分支
//開另一輛只放一只貓的也有一個(gè)分支
import java.util.*;
public class Main{
    static int N=20;
    static int n,m;
    static int arr[]=new int [N];
    static int ans=N;
    static int car[]=new int [N];
    static int cat[]=new int[N];
    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        n=in.nextInt();
        m=in.nextInt();
        for(int i=0;i<n;i++)cat[i]=in.nextInt();
        Arrays.sort(arr,0,n);
        //從小到大排個(gè)序
        Reverse(arr,0,n-1);
        //再從大到小排個(gè)序，優(yōu)先放重貓
        dfs(0,0);
        System.out.println(ans);
    }
    //直接把他看成是第一遍模擬，剩下的遞歸處理即可。
    public static void dfs(int u,int k){
        if(k>=ans)return;
        if(u==n){
            //走到n時(shí)，即為找到答案ans=當(dāng)前小車的數(shù)量k
            ans=k;
            return;
        }
        //考慮貓都放一輛車的情況
        for(int i=0;i<k;i++){
            if(cat[u]+car[i]<=m){
                car[i]+=cat[u];
                dfs(u+1,k);
                car[i]-=cat[u];
                //恢復(fù)現(xiàn)場(chǎng),便于下一次加貓操作
            }
        }
        //考慮貓只放一輛車的情況
        car[k]=cat[u];
        dfs(u+1,k+1);
        //每次dfs會(huì)用到一輛車，所以需要加一。
        car[k]=0;
        //恢復(fù)現(xiàn)場(chǎng)
    }
    public static void Reverse(int q[],int l,int r)
    //反轉(zhuǎn)函數(shù) -->從大到小排個(gè)序
    {
        for(int i=l,j=r;i<j;i++,j--){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
        }
    }
    
}

? ? ?
看到這里，不妨點(diǎn)個(gè)關(guān)注 ??文章來源地址http://www.zghlxwxcb.cn/news/detail-634000.html

到了這里，關(guān)于藍(lán)橋杯上岸每日N題 第七期(小貓爬山)?。?！的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！