【算法導論】貪心算法之活動安排問題

         對于許多最優化問題來說，采用動态規劃來求解最優解有點大材小用了，隻需要采用更簡單有效的貪心算法就行了。貪心算法就是所做的每一步選擇都是目前最佳的，通過局部最佳來尋求全局最佳解。就像砝碼稱重一樣，總是優先選擇大的砝碼。

         貪心算法對大多數優化問題來說能産生最優解，但也不一定總是這樣的。能用貪心算法解的典型問題包括活動選擇問題、最小生成樹、最短路徑問題等等。下面我們來讨論活動活動選擇問題：

          對于上面問題，貪心算法的思想就是：貪心選擇使得剩下的、未排程的時間最大化。在本例中，先選擇i=1,然後從xi>=x1的集合中選擇fi最小的，此時i=4,然後從x>=x4的集合中選擇fi最小的，此時i=8,然後從x>=x8的集合中選擇fi最小的，此時i=11.是以就可以得到問題的一個最優解。

具體程式實作如下：

作者：nineheadedbird