Greedy Algorithm

我们容易验证这个问题具有最优子结构性质。为了寻找最优子结构，定义如下的集合：\[S_{ij} = \{a_{k} \in S: f_{i} \leq s_{k} < f_{k} \leq s_{j} \}\]
显然， \(S_{ij}\) 是 \(S\) 中活动的子集，其中的每个活动都在活动 \(a_{i}\) 结束之后开始，且在活动 \(a_{j}\) 开始之前结束。

假设 \(S_{ij}\) 的最优解 \(A_{ij}\) 包含活动 \(a_{k}\) ，则显然 \(A_{ij}\) 也包含 \(S_{ik}\) 的最优解 \(A_{ik}\) 及 \(S_{kj}\) 的最优解 \(A_{kj}\) 。即有：\(A_{ij} = A_{ik} \cup \{ a_{k} \} \cup A_{kj}\) ，从而有：\[|A_{ij}| = |A_{ik}| + |A_{kj}| + 1 \]
上面递归式假设 \(k\) 值已知，然而我们并不知道。 \(k\) 的取值可能是 \(i+1, ..., j-1\) ，共有 \(j-i-1\) 种可能。于是： \[|A_{ij}| = \begin{cases} 0 & \text{if} \; S_{ij} = \emptyset, \\ \max \limits_{a_{k} \in S_{ij}} \{ |A_{ik}| + |A_{kj}| + 1 \} & \text{if} \; S_{ij} \neq \emptyset.\end{cases}\]

到此为止，已经得到一个递归解法，可根据这个递归式直接编程即可实现（运行效率低）。也可设计一个带备忘机制的递归算法，或者设计一个表格化的、自底向上基于前面递归式的动态规化算法。具体的编程实现略。

直观上，我们应该选择这样一个活动，选出它后剩下的资源应能被尽量多的其他活动所用。
现在考虑可选的活动，其中必然有一个最先结束。 所以我们应该每次选择 \(S\) 中最早结束的活动，因为剩下的资源可供尽量多的活动使用。

采用上面的贪心选择算法，由于 \(a_{1}\) 最先结束，所以选择活动 \(a_{1}\) ，按同样的方法在剩下活动中依次选择 \(a_{4}, a_{8}, a_{11}\) 。可以得到活动选择问题的一个解为： \(\{a_{1}, a_{4}, a_{8}, a_{11}\}\)

要证明它的正确性，只需要证明我们的第一个选择，即第一个最早结束的活动 \(a_{1}\) 在某个最大的兼容活动集中。这个结论是“显而易见”的。形式化的严谨证明可参考“算法导论，第 3 版，定理 16.1”。

说明：不能采用这样的贪心策略：“每次选择 \(S\) 中占用时间最少的活动”，因为它不一定得到正确解。比如下面例子中，如果“每次选择 \(S\) 中占用时间最少的活动”，则应该选择下排的三个活动，但事实上我们可以找到更多的兼容活动（上排的四个活动）。

+-----+--------+--------+   +-------+
|     |        |        |   |       |
1--2--3--4--5--6--7--8--9--10--11--12
|  |        |     |             |   |
+--+        +-----+             +---+

/* 贪心算法解决活动选择问题 */
#include<stdio.h>

void greedy_activity(int s[], int f[], int n) {
    int i = 1;                                       // 由于约定f按单调递增的顺序排列，所以可以总是选择a1。
    printf("The selected activities are: a%d ", i);
    int j;
    for (j=1; j<n; j++) {
        if (s[j] >= f[i]) {
            printf("a%d ", j+1);
            i = j;
        }
    }
    printf("\n");
}

int main() {
    int s[] =  {1, 3, 0, 5, 3, 5,  6,  8,  8,  2, 12};   // 活动开始时间
    int f[] =  {4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16};   // 活动结束时间
    int n = sizeof(s)/sizeof(s[0]);

    greedy_activity(s, f, n);

    return 0;
}

要使得背包里装的物品价值最大，那我们贪心地每次选取那些单位价值最高（即 \(v_i/w_i\) 最高）的物品可以吗？通过下面的例子我们可以发现这种贪心策略不可取。假设背包最多可承重 10kg，现在有 2 种物品，重量和价值为 2kg，10kg 和 4，8。按照前面的贪心策略，我们会选取物品 1（因为它的单位价值最高），此时由于背包承重的限制我们无法再选择物品 2 了。而显然这个问题的解是选择物品 2（价值为 8）。

我们需要换一种思路。假设问题的解为物品 \(a_1, a_2, \cdots, a_k\) ，此时如果把最后一个物品 \(a_k\) 拿掉，则对于剩下的 \(k-1\) 个物品 \(a_1, a_2, \cdots, a_{k-1}\) 来说它的重量范围为 \(0 \sim (W-w_k)\) ，而且用反证法可以推导它是其子问题（即背包总承重为 \(W-w_k\) 的背包问题）的最优解。

上面的推理表明“0-1 背包问题的最优解中包含其子问题的最优解”。具有这个特点的问题往往可以用“动态规划”来解决。

基于上面的推理，下面介绍使用“动态规划”解决 0-1 背包问题的过程。我们定义 函数 \(m[i, w]\) 表示到第 \(i\) 个物品为止，在限制总重量为 \(w\) 的情况下我们所能选择到的最优解对应的总价值。则 0-1 背包问题最优解对应的总价值就是 \(m[n, W]\) 。

显然，有下面推导关系：
\[m[i, w] = \begin{cases} 0 & \text{if} \; i=0 \; \text{or} \; w=0 \\ m[i-1, w] & \text{if} \; w_i > w \\ \max(m[i-1,w], m[i-1,w-w_i] + v_i) & \text{if} \; w_i \le w \\ \end{cases}\]

下面的伪代码可以解决 0-1 背包问题：

// pseudo code for 0-1 knapsack problem

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)

for j from 0 to W do:
    m[0, j] := 0

for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

算法的时间复杂度为 \(O(nW)\) 。

参考：https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem

可以用贪心算法解决“部分背包问题”。贪心策略是： 优先选取单位价值最高的物品，直到达到背包的重量限制。