搜索(bfs-和-dfs)-資料下載頁
2025-07-25 08:21本頁面
【正文】 些硬幣組合，能否得到 n，如果能，使用硬幣最少的情況下，怎么組合？ 樣例輸入： 5 9 9 9 37 樣例輸出： Dispense 1 quarters, 1 dimes, 0 nickels, and 2 pennies. 一個(gè)例題 含有前面對(duì)討論 DFS 狀態(tài)的搜索中需要達(dá)到的“ 最優(yōu) ” 要求，也涉及到剪枝 分析： 一共四層 在 k 層，依次用 0， 1， … num[k] 個(gè)硬幣，遞 歸調(diào)用 DFS（ k+1） , 直到最后一層 在最后一層判斷能否組合成 n， 如果能，記錄當(dāng)前狀態(tài) 和 最優(yōu)狀態(tài)的較優(yōu)值 一個(gè)例題 void dfs(int k) { if (k == 3) { if (能組合成 n) 記錄較優(yōu)結(jié)果 回溯 } for (int i = 0。 i =num[i]。 i++) { 取 i 枚當(dāng)前價(jià)值的硬幣 dfs（ k+1） } } 一個(gè)例題 void dfs(int k) { if (k == 3) { if (能組合成 n) 記錄較優(yōu)結(jié)果 回溯 } for (int i = 0。 i =num[i]。 i++) { 取 i 枚當(dāng)前價(jià)值的硬幣 dfs（ k+1） } } 一個(gè)例題 細(xì)節(jié)問題： 什么叫取出當(dāng)前價(jià)值的 i 枚硬幣？ 如果當(dāng)前硬幣取 i 枚后，所得到的數(shù)已經(jīng)大于 n？ 回溯過程需要還原成上一層狀態(tài)，怎么實(shí)現(xiàn)？ 是不是真的需要每層執(zhí)行 O（ num[k]） 次？ DFS 其他問題 復(fù)雜度大，在使用之前分析能否接受 狀態(tài)的表示，以及每次回溯后，狀態(tài)都要還原成上一層狀態(tài) 剪枝 more? 具體情況，寫法當(dāng)然不一樣 一些練習(xí)題目 BFS: 2194 Mine 2470 Robot in Maze 1132 Knight Moves DFS: 1398 Square 3169 Back to the Barn 2273 Making Change 建議初學(xué)同學(xué)可以先自己動(dòng)手寫寫兩個(gè)引例 other 練習(xí)題目 發(fā)信人 : hawk (焚書煲粥 | hawk = Cai Niao Hawk), 信區(qū) : ACM 標(biāo) 題 : TOJ 簡單題 題號(hào) 發(fā)信站 : 天大求實(shí) BBS (Tue Oct 10 13:20:34 2022), 本站() 上次給我同學(xué)列的，都是我剛接觸時(shí)做的題， 供新加入的同學(xué)們上上手，也供學(xué)習(xí) C/C++ 的同學(xué)提高代碼能力 ~ 順序是亂排的。大家湊合著看： . . . . 膜拜 hawk? Thank you for your attending
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1