貪心的孩子的故事五篇范文(編輯修改稿)
2024-11-04 12:39 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。比如說(shuō)找最少硬幣個(gè)數(shù)的問(wèn)題。在算法的實(shí)現(xiàn)過(guò)程中，當(dāng)剩余的錢數(shù)大于2角5分時(shí)，我們?cè)谟涗浾?角5分硬幣的個(gè)數(shù)的變量里面加一，同時(shí)把剩余所找的錢的總數(shù)目也減2角5分。不斷重復(fù)這個(gè)過(guò)程，直到剩余所需找的錢的數(shù)目小于2角5分時(shí)，在記錄找1角硬幣的個(gè)數(shù)的變量里面加一，同時(shí)把剩余所找的錢的總數(shù)目也減1角，不斷重復(fù)這個(gè)過(guò)程，直到剩余所需找的錢的數(shù)目小于1角。5分和1分的硬幣實(shí)現(xiàn)過(guò)程同上述過(guò)程一樣，一直執(zhí)行到所剩的錢的數(shù)目為0，此時(shí)停止計(jì)算，得到最優(yōu)解。五、實(shí)驗(yàn)結(jié)果分析（1）最少加油次數(shù)當(dāng)加油后行駛的最大距離小于相鄰站點(diǎn)的最小值時(shí)，此時(shí)，可行，求解結(jié)果如下：當(dāng)加油后行駛的最大距離大于相鄰站點(diǎn)的最小值時(shí)，此時(shí)，沒(méi)用可行性，為邊沿情況，求解結(jié)果如下：（分析時(shí)空復(fù)雜性，設(shè)計(jì)測(cè)試用例及測(cè)試結(jié)果）時(shí)間復(fù)雜性：該算法的時(shí)間復(fù)雜度為O(n)空間復(fù)雜性分析：該算法的空間復(fù)雜度為O(1)（2）最少硬幣問(wèn)題 當(dāng)輸入的找零錢數(shù)為正常的時(shí)候的運(yùn)行情況如下：當(dāng)輸入的找零錢數(shù)為不正常的時(shí)候（為負(fù)）的運(yùn)行情況如下：（分析時(shí)空復(fù)雜性，設(shè)計(jì)測(cè)試用例及測(cè)試結(jié)果）時(shí)間復(fù)雜性：該算法的時(shí)間復(fù)雜性為O(n)空間復(fù)雜性分析：該算法的空間復(fù)雜性為O(1)六、實(shí)驗(yàn)體會(huì)貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹問(wèn)題，相容活動(dòng)安排問(wèn)題等。這樣和采用動(dòng)態(tài)規(guī)劃的算法相比，算法的思想更加的簡(jiǎn)單，實(shí)現(xiàn)起來(lái)更加的容易。但是也要明確貪心算法和動(dòng)態(tài)規(guī)劃的主要區(qū)別。及01背包問(wèn)題可以用動(dòng)態(tài)規(guī)劃算法求解，但是貪心選擇算法卻不能用動(dòng)態(tài)規(guī)劃算法求解。因?yàn)樨?
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1