Greedy.md

August 5, 2016 · View on GitHub

Greedy(貪心) Back

  • 動態規劃策略中問題的求解推給子問題時, 會有多種路徑選擇. 然而當我們事先已知道某路徑是最優時, 則並不需要再去選擇路徑, 而直接選擇該條最優路徑. 或者我們並不知道全局的最有答案, 但當前我們認為該選擇是最優 (局部最優)的時候, 則將採用貪心策略.
  • Sometimes loose, sometimes win

典型問題及算法

  • Activity-Selection Problem [details]
  • Fractional Knapsack Problem [details]
  • Single-source Shortest Path Problem