### 活动安排问题

$0 \leq s_i < f_i < \infty$. 也就是说$a_i$占用舞台的时间段为
$[s_i, f_i]$。那么安排的活动之间必须满足一个条件，那就是各自的时间段之

i1234567891011
$s_i$130535688212
$f_i$4567991011121416

### 贪心算法的基本内容

greedy-choice property: we can assemble a globally optimal
solution by making a locally optimal (greedy) choice. In other words,
when we are considering which choice to make, we make the choice that
looks best in the current problem, without considering results from
subproblems.

#### 0-1背包和部分背包问题

The 0-1 knapsack problem is the following. A thief robbing a
store finds n items; the ith item is worth $v_i$ dollars
and weighs $w_i$ pounds, where $v_i$ and $w_i$ are integers.
He wants to take as valuable a load as possible, but he can carry at
most W pounds in his knapsack for some integer W. Which items should
he take? (This is called the 0-1 knapsack problem because each item must
either be taken or left behind; the thief cannot take a fractional
amount of an item or take an item more than once.)

In the fractional knapsack problem, the setup is the same, but
the thief can take fractions of items, rather than having to make a
binary (0-1) choice for each item. You can think of an item in the 0-1
knapsack problem as being like a gold ingot, while an item in the
fractional knapsack problem is more like gold dust.

(a) The thief must select a subset of the three items shown whose
weight must not exceed 50 pounds. (b) The optimal subset includes
items 2 and 3. Any solution with item 1 is suboptimal, even though
item 1 has the greatest value per pound. (c) For the fractional
knapsack problem, taking the items in order of greatest value per
pound yields an optimal solution.

0-1背包不能用贪心策略来求解，但动态规划确实使用它的。