贪心算法 ——硬币兑换、区间调度、

硬币兑换：

from book：挑战程序设计竞赛

 思路：优先使用大面额兑换即可

package mainimport "fmt"func main() {results := []int{}//记录每一种数额的张数A := 620B := A//备份cnts := 0 //记录至少需要多少张nums := []int{1, 5, 10, 50, 100, 500}limits := []int{3, 2, 1, 3, 0, 2} //面额张数限制for i := len(nums) - 1; i >= 0; i-- {//nums_i 最多使用n张n := my_min(A/nums[i], limits[i])cnts += nresults = append(results, n)A -= nums[i] * n}fmt.Print("A:\n", B, "cnts:\n", cnts)fmt.Print(results)}func my_min(a, b int) int {if a < b {return a}return b
}

区间调度： 

 思路：

为了完成尽可能多的工作：需要i-1项工作尽可能的早结束，i项任务尽早的开始