算法竞赛入门经典（第二版），贪心法

贪心

背包相关问题：

最优装载问题：

给出n个物体，第i个问题的重量为wi。选择尽量多的物体，使得总重量不超过C。
只关心物体数量，装轻的比较划算。只需要把所有物体由重量由小
到大排序。

部分背包问题：

有n个物体，第i个物体的重量为wi,价值为vi。在总重量不超过C的情
况下让总价值尽量高。
每一个物体都可以只取走一部分，价值和重量按比例计算。

优先选择性价比高的（价值除以重量的值大的）

乘船问题：

有n个人，第i个人重量为wi，每艘船的最大载重量均为C，且最多只能乘2个人，用最少的船装载所有人。

最轻的人i应该 选择 能够和他一起坐船的人中最重的人j 一起坐船，以使得浪费最少。

比j重的人只能自己一个人坐船，因为最轻的i都无法与他组队，团队里没有适合与他坐同一条船的人了。

固，i从最小开始，j从最大开始：
i左移，j右移，寻找最优解。

区间相关问题

hdu1050
数轴上有n个开区间（ai,bi）。选择尽量多个区间，是的这些区间两两没有公共点。

将区间按bi从小到大的顺序排列，优先选择第一个区间，然后排除所有与之相交的区间。

区间选点问题

数轴上有n个闭区间[ai,bi]。取尽量少的点，使得每个区间内至少都有一个点（不同区间内含的点可以是同一个）。

把所有区间按b从小到大排序（b相同时，a从大到小排序），取最后一个点。

区间覆盖问题

数轴上有n个区间[ai,bi]，选择尽量少的区间覆盖一条指定线段[s,t]。

选择落在[s,t]之间的区间，按a排序，优先选择区间长度长的。