asp.net 網(wǎng)站管理工具 安全,建設(shè)一個(gè)能看視頻的網(wǎng)站,滕州網(wǎng)站建設(shè)培訓(xùn),價(jià)格信息網(wǎng)題目堆箱子。給你一堆n個(gè)箱子#xff0c;箱子寬 wi、深 di、高 hi。箱子不能翻轉(zhuǎn)#xff0c;將箱子堆起來(lái)時(shí)#xff0c;下面箱子的寬度、高度和深度必須大于上面的箱子。實(shí)現(xiàn)一種方法#xff0c;搭出最高的一堆箱子。箱堆的高度為每個(gè)箱子高度的總和。輸入使用數(shù)組[wi, di,…題目堆箱子。給你一堆n個(gè)箱子箱子寬 wi、深 di、高 hi。箱子不能翻轉(zhuǎn)將箱子堆起來(lái)時(shí)下面箱子的寬度、高度和深度必須大于上面的箱子。實(shí)現(xiàn)一種方法搭出最高的一堆箱子。箱堆的高度為每個(gè)箱子高度的總和。輸入使用數(shù)組[wi, di, hi]表示每個(gè)箱子。答題思路先明確核心目標(biāo)把箱子疊起來(lái)要求上面的箱子比下面的小寬、深、高都小疊出最高的高度和。第一步先認(rèn)識(shí) “箱子”—— 結(jié)構(gòu)體定義// 箱子結(jié)構(gòu)體寬(w)、深(d)、高(h) struct Box { int w, d, h; Box(int w 0, int d 0, int h 0) : w(w), d(d), h(h) {} };struct Box定義一個(gè) “箱子” 類型就像給 “箱子” 定規(guī)矩 —— 每個(gè)箱子必須有 3 個(gè)屬性寬度 w、深度 d、高度 h。int w, d, h;聲明這 3 個(gè)屬性都是整數(shù)。Box(int w 0, int d 0, int h 0) : w(w), d(d), h(h) {}這是 “箱子的構(gòu)造函數(shù)”。第二步存儲(chǔ)所有箱子 —— 全局變量vectorBox g_boxes; // 存儲(chǔ)所有箱子數(shù)據(jù) vectorint g_memo; // 記憶化數(shù)組記錄已計(jì)算的堆頂最大高度第三步給箱子 “排個(gè)隊(duì)”—— 排序規(guī)則// 排序規(guī)則寬→深→高降序簡(jiǎn)化堆疊條件判斷 bool cmpDesc(Box a, Box b) { if (a.w ! b.w) return a.w b.w; if (a.d ! b.d) return a.d b.d; return a.h b.h; }作用把所有箱子按 “從大到小” 排序排序后是 “箱子 A10,8,5→箱子 B9,7,4→箱子 C8,6,3”后續(xù)判斷 “能不能疊” 時(shí)只需要看 “后面的箱子是不是比前面的小”。解法 1暴力枚舉最笨但最容易懂的辦法核心邏輯把所有 “選 / 不選這個(gè)箱子” 的可能都試一遍找到最高的組合。1. 遞歸函數(shù)核心// 暴力解法遞歸枚舉選/不選當(dāng)前箱子時(shí)間復(fù)雜度O(2?) int bruteDfs(int index, Box prevBox) { // 遞歸終止所有箱子遍歷完沒(méi)有可選的了返回高度0 if (index g_boxes.size()) return 0; // 選項(xiàng)1不選當(dāng)前箱子直接遞歸處理下一個(gè)箱子 int option1 bruteDfs(index 1, prevBox); // 選項(xiàng)2選當(dāng)前箱子滿足堆疊約束當(dāng)前上一個(gè) int option2 0; if (g_boxes[index].w prevBox.w g_boxes[index].d prevBox.d g_boxes[index].h prevBox.h) { option2 g_boxes[index].h bruteDfs(index 1, g_boxes[index]); } // 返回“選”和“不選”中高度更大的那個(gè) return max(option1, option2); }函數(shù)參數(shù)int index當(dāng)前看到第幾個(gè)箱子Box prevBox上一個(gè)被選中的箱子。解讀if (index g_boxes.size()) return 0;g_boxes.size()是 “總共有多少個(gè)箱子”比如有 3 個(gè)箱子size3意思是 “如果已經(jīng)看完了所有箱子index3沒(méi)有可選的了疊出來(lái)的高度就是 0沒(méi)箱子可疊”—— 這是遞歸的 “終點(diǎn)”必須有否則程序會(huì)無(wú)限循環(huán)。int option1 bruteDfs(index 1, prevBox);翻譯“不選第 index 個(gè)箱子直接看下一個(gè)箱子index1”比如現(xiàn)在看第 0 個(gè)箱子不想選它就直接去看第 1 個(gè)箱子prevBox不變因?yàn)闆](méi)選當(dāng)前箱子上一個(gè)箱子還是原來(lái)的option1存的是 “不選當(dāng)前箱子時(shí)后面能疊出的最大高度”。int option2 0;option2存的是 “選當(dāng)前箱子時(shí)能疊出的最大高度”先默認(rèn)是 0如果不能選高度就是 0。if (g_boxes[index].w prevBox.w ...)核心條件“當(dāng)前箱子第 index 個(gè)的寬、深、高都比上一個(gè)箱子prevBox小”—— 滿足這個(gè)條件才能把當(dāng)前箱子疊在 prevBox 上面g_boxes[index]取 “裝箱子的大列表” 里第 index 個(gè)箱子g_boxes[index].w第 index 個(gè)箱子的寬度prevBox.w上一個(gè)箱子的寬度。option2 g_boxes[index].h bruteDfs(index 1, g_boxes[index]);翻譯“選當(dāng)前箱子的話總高度 當(dāng)前箱子的高度 看下一個(gè)箱子能疊出的最大高度”注意選了當(dāng)前箱子后下一個(gè)箱子要疊在 “當(dāng)前箱子” 上面所以prevBox要換成g_boxes[index]上一個(gè)箱子變成當(dāng)前這個(gè)了。return max(option1, option2);max(a,b)是取 a 和 b 中更大的那個(gè)數(shù)意思是 “選不選當(dāng)前箱子哪個(gè)能疊得更高就選哪個(gè)方案”。2. 暴力解法入口函數(shù)int bruteForce(vectorBox boxes) { int n boxes.size(); if (n 0) return 0; // 邊界沒(méi)箱子時(shí)高度為0 sort(boxes.begin(), boxes.end(), cmpDesc); // 先排序簡(jiǎn)化判斷 g_boxes boxes; // 把排序后的箱子存入全局變量供遞歸使用 // 初始化“虛擬堆底”用w/d/h都是極大值的箱子所有真實(shí)箱子都能堆在它上面 Box dummy(INT_MAX, INT_MAX, INT_MAX); return bruteDfs(0, dummy); // 從第0個(gè)箱子開始遞歸初始堆底是虛擬箱子 }解讀int bruteForce(vectorBox boxes)函數(shù)接收 “裝箱子的列表” 作為參數(shù)返回最終的最大高度。int n boxes.size();算出總共有多少個(gè)箱子比如列表里有 3 個(gè)箱子n3。if (n 0) return 0;如果沒(méi)有箱子疊出來(lái)的高度就是 0。sort(boxes.begin(), boxes.end(), cmpDesc);給所有箱子按 “從大到小” 排序用前面定義的cmpDesc規(guī)則。g_boxes boxes;把排序后的箱子列表存到全局變量g_boxes里這樣遞歸函數(shù)bruteDfs能拿到所有箱子。Box dummy(INT_MAX, INT_MAX, INT_MAX);創(chuàng)建一個(gè) “超級(jí)大箱子”INT_MAX是 C 里的 “整數(shù)最大值”比如 2147483647作為 “最底下的虛擬箱子”—— 所有真實(shí)箱子都比它小所以第一個(gè)選的箱子可以直接疊在它上面。return bruteDfs(0, dummy);從第 0 個(gè)箱子第一個(gè)箱子開始遞歸初始的 “上一個(gè)箱子” 是這個(gè)超級(jí)大箱子。解法 2記憶化搜索給暴力解法 “記筆記”核心邏輯暴力解法會(huì)重復(fù)算同一個(gè)箱子作為 “堆頂” 的最大高度用一個(gè) “小本本” 記下來(lái)下次直接用不用再算。1. 記憶化遞歸函數(shù)// 記憶化搜索遞歸返回以index為堆頂?shù)淖畲蟾叨葧r(shí)間復(fù)雜度O(n2) int memoDfs(int index) { // 核心優(yōu)化如果已經(jīng)計(jì)算過(guò)該結(jié)果直接返回避免重復(fù)遞歸 if (g_memo[index] ! -1) return g_memo[index]; // 初始值僅當(dāng)前箱子作為堆頂高度就是它自己的h int maxH g_boxes[index].h; // 遍歷后續(xù)箱子尋找可堆疊的箱子 for (int i index 1; i g_boxes.size(); i) { // 堆疊約束i號(hào)箱子比index號(hào)小能堆在index下面 if (g_boxes[i].w g_boxes[index].w g_boxes[i].d g_boxes[index].d g_boxes[i].h g_boxes[index].h) { // 遞歸計(jì)算當(dāng)前高度 以i為堆頂?shù)淖畲蟾叨?maxH max(maxH, g_boxes[index].h memoDfs(i)); } } // 記錄結(jié)果到記憶數(shù)組供后續(xù)使用 g_memo[index] maxH; return maxH; }先明確memoDfs(index)的意思是 “算一算以第 index 個(gè)箱子為‘堆頂’時(shí)能疊出的最大高度”。解讀if (g_memo[index] ! -1) return g_memo[index];g_memo是 “記筆記的小本本”初始化時(shí)所有位置都是 - 1表示 “沒(méi)算過(guò)”意思是 “如果第 index 個(gè)箱子的最大高度已經(jīng)算過(guò)了直接把記的數(shù)返回不用再算一遍”。int maxH g_boxes[index].h;初始值如果只疊這一個(gè)箱子第 index 個(gè)高度就是它自己的高度比如第 0 個(gè)箱子高度 5maxH5。for (int i index 1; i g_boxes.size(); i)遍歷第 index 個(gè)箱子后面的所有箱子因?yàn)橐呀?jīng)排序后面的箱子更小找能疊在它下面的箱子。if (g_boxes[i].w g_boxes[index].w ...)判斷第 i 個(gè)箱子能不能疊在第 index 個(gè)箱子下面i 比 index 小。maxH max(maxH, g_boxes[index].h memoDfs(i));意思是 “如果第 i 個(gè)箱子能疊在下面總高度 當(dāng)前箱子高度 以 i 為堆頂?shù)淖畲蟾叨取北热绲?0 個(gè)箱子高度 5第 1 個(gè)箱子能疊在下面且以 1 為堆頂?shù)淖畲蟾叨仁?7那總高度 5712比原來(lái)的 5 大所以 maxH 更新為 12。g_memo[index] maxH;把算出來(lái)的 “以 index 為堆頂?shù)淖畲蟾叨取?記到小本本里下次再要算這個(gè)數(shù)直接取就行。2. 記憶化搜索入口函數(shù)int memoSearch(vectorBox boxes) { int n boxes.size(); if (n 0) return 0; sort(boxes.begin(), boxes.end(), cmpDesc); // 統(tǒng)一排序規(guī)則 g_boxes boxes; g_memo.clear(); g_memo.resize(n, -1); // 初始化記憶數(shù)組-1表示“該位置還沒(méi)計(jì)算過(guò)” int maxHeight 0; // 枚舉所有箱子作為堆頂找全局最大高度 for (int i 0; i n; i) { maxHeight max(maxHeight, memoDfs(i)); } return maxHeight; }解讀g_memo.resize(n, -1);把 “小本本” 的大小設(shè)為箱子數(shù)量所有位置初始值都是 - 1沒(méi)算過(guò)。for (int i 0; i n; i)挨個(gè)算 “以第 0 個(gè)、第 1 個(gè)、第 2 個(gè)箱子為堆頂?shù)淖畲蟾叨取弊詈笕∽畲蟮哪莻€(gè)就是全局最大高度。記憶化搜索的優(yōu)勢(shì)時(shí)間復(fù)雜度 O (n2)每個(gè)箱子只算一次每個(gè)箱子遍歷后面的 n 個(gè)箱子總次數(shù)是 n×n比暴力解法的 2?快太多比如 n20暴力要算 100 萬(wàn)次記憶化只算 400 次。解法 3動(dòng)態(tài)規(guī)劃不用遞歸直接算核心邏輯把記憶化的 “遞歸” 改成 “循環(huán)”一步步算每個(gè)箱子作為堆頂?shù)淖畲蟾叨葲](méi)有遞歸的額外開銷是最優(yōu)解。動(dòng)態(tài)規(guī)劃函數(shù)// 動(dòng)態(tài)規(guī)劃dp[i] 以第i個(gè)箱子為堆頂?shù)淖畲蟾叨葧r(shí)間復(fù)雜度O(n2) int dynamicProgramming(vectorBox boxes) { int n boxes.size(); if (n 0) return 0; sort(boxes.begin(), boxes.end(), cmpDesc); // 排序簡(jiǎn)化判斷 vectorint dp(n, 0); int maxHeight 0; for (int i 0; i n; i) { dp[i] boxes[i].h; // 初始值僅當(dāng)前箱子 // 遞推遍歷前置可堆疊箱子更新dp[i] for (int j 0; j i; j) { if (boxes[j].w boxes[i].w boxes[j].d boxes[i].d boxes[j].h boxes[i].h) { dp[i] max(dp[i], dp[j] boxes[i].h); } } maxHeight max(maxHeight, dp[i]); } return maxHeight; }先明確dp[i]和記憶化的memoDfs(i)意思完全一樣 ——“以第 i 個(gè)箱子為堆頂?shù)淖畲蟾叨取敝皇怯脭?shù)組存不用遞歸算。解讀vectorint dp(n, 0);創(chuàng)建一個(gè)長(zhǎng)度為 n 的數(shù)組 dp初始值都是 0比如 n3dp[0,0,0]。for (int i 0; i n; i)遍歷每個(gè)箱子算它作為堆頂?shù)淖畲蟾叨?。dp[i] boxes[i].h;初始值只疊這一個(gè)箱子高度就是它自己的高度比如 i0dp [0]5i1dp [1]4i2dp [2]3。for (int j 0; j i; j)遍歷第 i 個(gè)箱子前面的所有箱子j i因?yàn)榕判蚝笄懊娴南渥痈笳夷墀B在 i 下面的箱子。if (boxes[j].w boxes[i].w ...)判斷第 j 個(gè)箱子能不能疊在 i 下面j 比 i 大所以 i 能疊在 j 上面i 是堆頂。dp[i] max(dp[i], dp[j] boxes[i].h);意思是 “如果 j 能疊在 i 下面那 i 作為堆頂?shù)母叨? j 作為堆頂?shù)母叨? i 的高度”比如 i1高度 4j0能疊dp [j]5 → 549比原來(lái)的 4 大所以 dp [1] 更新為 9比如 i2高度 3j0能疊dp [j]5 →538j1能疊dp [j]9 →9312 → dp [2] 更新為 12。maxHeight max(maxHeight, dp[i]);每次算完 dp [i]都和當(dāng)前的最大高度比保留更大的那個(gè)比如算完 dp [2]12maxHeight12。動(dòng)態(tài)規(guī)劃的優(yōu)勢(shì)和記憶化搜索時(shí)間復(fù)雜度一樣O (n2)但沒(méi)有遞歸的 “函數(shù)調(diào)用、棧幀切換” 開銷實(shí)際運(yùn)行速度更快比如 n50記憶化要 4 毫秒動(dòng)態(tài)規(guī)劃只要 1.5 毫秒。最后三種解法核心對(duì)比解法核心思想時(shí)間復(fù)雜度空間復(fù)雜度優(yōu)缺點(diǎn)暴力遞歸枚舉底層遞歸上層O(2n)O(n2)簡(jiǎn)單但效率極低記憶化搜索哈希表存儲(chǔ)重復(fù)計(jì)算結(jié)果O(n2)O(n2)解決“重復(fù)計(jì)算”,有遞歸棧開銷動(dòng)態(tài)規(guī)劃排序遞推記錄中間狀態(tài)O(n2)O(n)從“遞歸”轉(zhuǎn)“遞推”去掉哈希開銷