贪心策略的基本要素

贪心算法通过一系列选择得到最优解，每一步都选择当前看来最优的选项。步骤一般如下：

1. 确定问题的最优子结构（optimal substructure）：
   • 一个问题具有最优子结构意味着：问题的最优解可以由其子问题的最优解组合得到。
   • 例子：活动选择问题 $S_{ij}$，选择活动 $a_k$ 后，剩下的子问题是 $S_{ik}$ 和 $S_{kj}$。
2. 构造递归解法：
   • 将问题表示为递归形式，但不一定使用动态规划求解。
   • 例如活动选择问题递归公式：
     $$c[i,j]=\{\begin{array}{ll}0& S_{ij}=\varnothing \\ {\max }_{a_k\in S_{ij}}c[i,k]+c[k,j]+1& \text{否则}\end{array}$$
3. 确定贪心选择后的唯一子问题：
   • 选择贪心活动后，只剩一个子问题需要解决。
   • 活动选择：选择最早结束的活动 $a_1$ 后，只需考虑 $S_1=a_i|s_i\ge f_1$。
4. 证明贪心选择是安全的：
   • 必须保证每次贪心选择可以出现在某个最优解中。
   • 例：活动选择定理 15.1 证明选择最早结束活动总能得到最优解。
5. 设计递归贪心算法：
   • 递归实现，每次选择贪心活动，然后递归处理剩余子问题。
6. 转换为迭代算法：
   • 将递归改为迭代，通常效率更高，易实现。

贪心算法与动态规划的区别

贪心选择性质：通过局部最优选择得到全局最优解。
最优子结构：问题的最优解包含子问题最优解。

例题：背包问题对比

1. 0-1 背包问题：
   • 每件物品不可拆分，目标最大化总价值。
   • 贪心选择按“单位重量价值最高”可能失败：
     • 示例：
       $$W=50,\{\begin{array}{l}item1:w=10,v=60\\ item2:w=20,v=100\\ item3:w=30,v=120\end{array}$$
     • 贪心选 item1 → 剩余容量 40 → 无法得到最优解 220（选 item2 + item3）。
2. 分数背包问题：
   • 允许取物品部分重量。
   • 贪心选择按单位重量价值排序，每次取尽可能多的高价值物品 → 最优解。
   • 时间复杂度：$O(n\log n)$（排序）或 $O(n)$（选择性算法）。
     总结：

• 0-1 背包 → 动态规划适用。
• 分数背包 → 贪心策略可行。

贪心策略设计步骤总结

1. 将优化问题表示为选择一个活动/元素后只剩一个子问题。
2. 证明贪心选择安全，即该选择可出现在最优解中。
3. 利用最优子结构证明：贪心选择 + 子问题最优解 = 原问题最优解。

练习题示例解析

1. 15.2-1 分数背包的贪心性质：
   • 贪心按单位重量价值排序，每次取尽可能多 → 全局最优。
2. 15.2-2 0-1 背包动态规划：
   • DP 状态 $DP[i][w]$ = 前 $i$ 个物品在容量 $w$ 下最大价值
     $$DP[i][w]=\max (DP[i-1][w],DP[i-1][w-w_i]+v_i)$$
3. 15.2-3 特殊排序的 0-1 背包：
   • 如果按重量升序 = 按价值降序 → 贪心策略即可，直接选物品直到容量耗尽。
4. 15.2-4 最少水站问题：
   • 贪心选择下一个能到达最远的水站 → 保证最少停靠。
5. 15.2-5 最小单位区间覆盖问题：
   • 按点排序，每次选择能覆盖最右端的单位区间 → 贪心可得最少区间。
6. 15.2-6 分数背包 $O(n)$ 实现：
   • 利用选择算法（如 Quickselect）找到中位数分界点 → 部分排序 → 线性时间解决。
7. 15.2-7 最大化 $\Sigma a_i{b}_i$ 问题：
   • 将 $A$ 与 $B$ 排序，同序匹配即可，贪心策略正确。

给出几个典型问题的 C++ 实现，包含详细注释。下面我先给 活动选择问题 和 分数背包问题 的贪心算法实现示例。

1. 活动选择问题（贪心算法）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义活动结构体
struct Activity {
    int start;  // 活动开始时间
    int finish; // 活动结束时间
};
// 贪心算法选择最大兼容活动集合
vector<Activity> greedyActivitySelector(vector<Activity>& activities) {
    vector<Activity> selected; // 存放选择的活动集合
    int n = activities.size();
    if (n == 0) return selected; // 如果没有活动，直接返回空集合
    // 按活动结束时间升序排序
    // 这是贪心策略的关键：总是选择最早结束的活动
    sort(activities.begin(), activities.end(), [](Activity a, Activity b) {
        return a.finish < b.finish;
    });
    selected.push_back(activities[0]); // 选择第一个活动（最早结束的活动）
    int lastFinish = activities[0].finish; // 记录上一个被选择活动的结束时间
    // 遍历剩下的活动
    for (int i = 1; i < n; i++) {
        // 如果当前活动的开始时间 >= 上一个选择活动的结束时间，则兼容
        if (activities[i].start >= lastFinish) {
            selected.push_back(activities[i]);  // 将当前活动加入结果集合
            lastFinish = activities[i].finish; // 更新上一个活动结束时间
        }
        // 否则跳过当前活动，继续检查下一个活动
    }
    return selected; // 返回最大兼容活动集合
}
int main() {
    // 定义待选择的活动集合（未必按结束时间排序）
    vector<Activity> activities = {
        {1, 4}, {3, 5}, {0, 6}, {5, 7},
        {3, 9}, {5, 9}, {6, 10}, {8, 11},
        {8, 12}, {2, 14}, {12, 16}
    };
    // 调用贪心算法，选择最大兼容活动集合
    vector<Activity> result = greedyActivitySelector(activities);
    // 输出结果
    cout << "Selected activities:\n";
    for (auto act : result) {
        cout << "[" << act.start << ", " << act.finish << "] ";
    }
    cout << endl;
    return 0;
}

注释解释贪心思想：

1. 排序：按结束时间升序排序是贪心选择的核心，它保证每次选择活动时留下最多空间给后续活动。
2. 选择第一个活动：总是选择最早结束的活动作为起点。
3. 检查兼容性：只选择与已选活动不冲突的活动。
4. 时间复杂度：排序 $O(n\log n)$ + 遍历 $O(n)$ → 总体 $O(n\log n)$。

2. 分数背包问题（贪心算法）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义物品结构体
struct Item {
    int value;  // 物品价值
    int weight; // 物品重量
};
// 贪心算法求分数背包最大价值
double fractionalKnapsack(vector<Item>& items, int W) {
    // 按单位重量价值 v/w 降序排序
    // 贪心策略：总是先放单位价值最高的物品
    sort(items.begin(), items.end(), [](Item a, Item b) {
        return (double)a.value / a.weight > (double)b.value / b.weight;
    });
    double totalValue = 0.0;      // 背包总价值
    int remainingWeight = W;      // 背包剩余容量
    // 遍历所有物品
    for (auto item : items) {
        if (item.weight <= remainingWeight) {
            // 当前物品可以完整放入背包
            totalValue += item.value;          // 增加背包总价值
            remainingWeight -= item.weight;    // 减少背包剩余容量
        } else {
            // 当前物品无法完整放入，只放入部分
            totalValue += item.value * ((double)remainingWeight / item.weight);
            break; // 背包已满，退出循环
        }
    }
    return totalValue; // 返回分数背包最大价值
}
int main() {
    // 定义物品集合，每个物品有价值和重量
    vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
    int W = 50; // 背包容量
    // 调用分数背包贪心算法
    double maxValue = fractionalKnapsack(items, W);
    cout << "Maximum value in fractional knapsack: " << maxValue << endl;
    return 0;
}

注释说明贪心思想：

1. 排序：按单位重量价值 $v_i/w_i$ 降序排列，保证每次选择“最值钱”的物品。
2. 完整放入：如果当前物品能放下，则直接放入，背包容量减少。
3. 部分放入：如果当前物品放不下，则只放入能放下的部分，背包容量耗尽。
4. 时间复杂度：排序 $O(n\log n)$ + 遍历 $O(n)$ → 总体 $O(n\log n)$。
5. 贪心性质：每次选择局部最优（单位价值最大），最终得到全局最优解。