閱讀(630) 書簽贊(0) 我要糾錯

C++貪心小結(jié)

2023-09-20 12:03 更新

貪心算法通常用于解決最優(yōu)化問題，其原理是在每個決策階段都做出局部最優(yōu)的決策，以期望獲得全局最優(yōu)解。
貪心算法會迭代地做出一個又一個的貪心選擇，每輪都將問題轉(zhuǎn)化成一個規(guī)模更小的子問題，直到問題被解決。
貪心算法不僅實(shí)現(xiàn)簡單，還具有很高的解題效率。相比于動態(tài)規(guī)劃，貪心算法的時(shí)間復(fù)雜度通常更低。
在零錢兌換問題中，對于某些硬幣組合，貪心算法可以保證找到最優(yōu)解；對于另外一些硬幣組合則不然，貪心算法可能找到很差的解。
適合用貪心算法求解的問題具有兩大性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。貪心選擇性質(zhì)代表貪心策略的有效性。
對于某些復(fù)雜問題，貪心選擇性質(zhì)的證明并不簡單。相對來說，證偽更加容易，例如零錢兌換問題。
求解貪心問題主要分為三步：問題分析、貪心策略確定、正確性證明。其中，貪心策略確定是核心步驟，正確性證明往往是難點(diǎn)。
分?jǐn)?shù)背包問題在 0-1 背包的基礎(chǔ)上，允許選擇物品的一部分，因此可使用貪心算法求解。貪心策略的正確性可以使用反證法來證明。
最大容量問題可使用窮舉法求解，時(shí)間復(fù)雜度為 $O (n^{2})$ 。通過設(shè)計(jì)貪心策略，每輪向內(nèi)移動短板，可將時(shí)間復(fù)雜度優(yōu)化至 $O (n)$ 。
在最大切分乘積問題中，我們先后推理出兩個貪心策略： $\geq 4$ 的整數(shù)都應(yīng)該繼續(xù)切分、最優(yōu)切分因子為 $3$ 。代碼中包含冪運(yùn)算，時(shí)間復(fù)雜度取決于冪運(yùn)算實(shí)現(xiàn)方法，通常為 $O (1)$ 或 $O (\log ? n)$ 。

以上內(nèi)容是否對您有幫助：

← C++最大切分乘積問題

寫筆記

我要補(bǔ)充

C++貪心 小結(jié)

C++貪心小結(jié)