Greedy(貪心) Back

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

典型問題及算法

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