貪婪vs動態​​

Question

我有一些關於算法的一般問題，當你遇到一些問題並且你想寫一些算法時，你如何處理這個問題，你如何決定使用貪婪算法或動態編程的算法？在此先感謝

Answer 1

一般來說，我嘗試將新問題轉化爲一個衆所周知的問題，有一個衆所周知的解決方案。然後選擇正確的算法是微不足道的。根據我的經驗，這涵蓋了大部分野外病例。

如果第一步失敗，我嘗試一個貪婪的方法，並試圖證明它不起作用。證明部分可能會很棘手，但基本上你必須證明在某個中間步驟中當地的最佳選擇不會產生整體最佳結果。從那裏我分開，通常動態是我嘗試的第一個選擇之一。

如果一切都失敗了，我開始尋找很好的近似算法，這些算法對於手頭的問題已經足夠接近了。許多問題可以通過在一小部分時間和資源上進行近似來「解決」問題得到解決，從而使其成爲明顯的贏家。

Answer 2

如果貪心算法會的工作，我會更喜歡，如果不是，那麼，如果動態編程的作品，然後選擇一個，否則事情較差漸近行爲。

你怎麼能認真期望得到你的問題的答案？

所有的動態規劃任務都有一個特點，即（良好選擇的）子問題的最優解決方案也是整個問題的最佳解決方案的一部分。要麼你發現有問題的問題，這個功能還是你不...

更新： 我想告訴你很好的回答說：「我把它映射到一個類似的衆所周知的問題，」但是這不是我所做的。我解決了一些DP問題，從那以後，如果我看到用蠻力算法產生O（2^n）的東西，我會自動開始搜索可以構造最優解的子問題。