贪心算法入门

贪心算法的核心思想是通过局部最优解得到或近似取得全局最优解, 此时有几个待解决的问题:

1. 怎么判断题目是否应用贪心策略求解?
2. 怎么寻求局部最优与全局最优的关系?
3. 如何选择最优的贪心标准以得到全局最优/较优解?

思想理解

可以参阅知乎答主"冒泡"的一篇回答 如何理解动态规划?
与 Aditya Bhargava 的算法图解

例题理解

背包问题: 策略选择?

有一个背包, 容量为 150 kg.
有 7 个物品, 要求尽可能让装入背包中物品总价值最大, 且不能超过总容量
请你计算应如何取舍

重量 (kg)	35	30	60	50	40	10	25
价值 ($)	10	40	30	50	35	40	30

对于此题, 贪心的标准可能有几个?

1. 每次选价值最大的
2. 每次选重量最轻的
3. 每次选单位重量价值最高的

试将所有策略与之对应的结果求出如下

策略 1: \(50 + 40 + 40 + 30 = 165 (130 kg)\)
策略 2: \(40 + 30 + 40 + 10 + 35 = 155 (140 kg)\)
策略 3: \(40 + 40 + 30 + 50 + 10 = 170(150kg)\)

哪种是最优解?
策略 3 吗? 如果更改数据呢?

以上三策略都是错的:

要求尽可能让装入背包中物品总价值最大, 且不能超过总容量

题目的局限使得三种策略无对错可分, 原因在于策略 3 打破了题目的限制, 1 和 2 又没有显著的优势可分
因而此题不适合用贪心算法求解, 或者说, 用贪心在此题只能获得近似最优解.

我们解决了第一个问题: 具有某些限制性条件的题目不适合用贪心算法求解

这道题到底怎么解? 应使用动态规划

最优装载问题

给定一个最大载重量为 \(M\) 的卡车和 \(N\) 种食品
有食盐，白糖，大米等 (假设它们都是散装且大货车只受重量限制不受体积限制)
已知第 \(i\) 种食品的最多拥有 \(W_i\) 公斤，其商品价值为 \(V_i\) 元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。

这道题可以用贪心算法求解, 因为每一个物品都可以分割成单位块, 单位块的利益与总收益成正比, 也即局部最优与全局最优相统一的本质

解题方法: 先将单位块的利益降序排列, 用循环从开头取起, 直到不能取为止便是最优解

第二 & 三个问题迎刃而解

排队问题:

有 \(N\) 个人排队到 \(R\) 个水龙头去打水, 他们装满水桶的时间为 \(T_1\), \(T_2\), ...\(T_n\)为整数且各不相等, 应如何安排他们的打水顺序才能使他们所花时间最少?

可显然得出:

\(T_s = T_打 + T_等\)

通过脑中模拟反证, 可得出结论: 打水时间少的应排最前位以减少等待时间

线段去重

列出方案:

1. 去除交点最多的(要是一样长怎么办?)
2. 去除最长的(要是最长的没交点, 短的还有交点呢?)
3. 每次选取线段右端点坐标最小的线段, 保留这条线段, 并把和这条线段有公共部分的所有线段删除, 直到没有公共部分

贪心算法的要素

贪心策略

使用贪心策略解题, 一般来说需要进行多步的贪心选择
每次选择后, 原问题都会变成一个相似的, 且规模最小的问题
每一步都是当前看似最佳的选择, 且每一个选择都仅作一次.

最优子结构

如果问题的最优解包含子问题的最优解, 即问题具有最优子结构的性质
如背包问题中, 第一次选单位质量价值最大的, 是第一个问题的最优解, 第二次选单位质量价值, 也是第二个问题的最优解
注意: 最优子结构不是贪心算法独有的概念!
不是所有具有最优子结构的问题都可以用贪心算法求解, 因为贪心往往是 "盲目" 的, 有时我们更需要理性的动态规划

辨析子结构

贪心算法, 分治法, 动态规划三者都具有子结构, 核心思想也即通过求解子问题最后获得整体解, 三者有何不同?

从子结构关系上看

贪心算法和分治法的子结构是相互独立的, 而分治法的子结构是分级的, 贪心的同级子结构是顺序求解的 (注意: 我理解的贪心算法每次决策后生成的子结构在逻辑上与之前的同属一级)
相对的, 分治法的最小子结构可以直接求解 (即基线条件), 贪心算法是每步选择, 分布求解
动态规划的子结构是部分重合的 (又称重叠最优子结构).
通俗点说, 动态规划的子结构是依赖于同级之前的子结构的, 还要满足无后效性

从算法的实现上看

分治法是递归式生成子结构, 一直到生成基线条件, 后又通过递归式地返回每层子结构的结果, 自下而上地将它们合并成问题的解.
动态规划是将所有子问题只计算一次并记录下来, 以备后面的问题使用 (类似于记忆化存储, 只是分治法没有记忆化还能正常工作, 动态规划就不行), 以空间换时间, 之后的解依赖之前的解, 一般采用自底向上的递推方式求解.
贪心算法则是从上而下, 在每个阶段做一个贪心的选择, 不断将问题转换为规模更小的子问题, 并期望通过每次的局部最优选择达到全局最优

总结

如何判断题目是否适合使用贪心策略求解？

答：当题目具有某些限制性条件时，可能不适合使用贪心算法。例如，在背包问题中，要求尽可能让装入背包中物品总价值最大，并且不能超过总容量。选择策略1（每次选价值最大的）、策略2（每次选重量最轻的）或策略3（每次选单位重量价值最高的）都不满足题目的要求，所以贪心算法不适合求解这个问题。

如何寻求局部最优与全局最优的关系？

答：在最优装载问题中，每个物品可以分割成单位块，单位块的利益与总收益成正比。这符合局部最优解与全局最优解相统一的特点。因此，可以用贪心算法求解这个问题。解题方法是将单位块的利益降序排列，从头开始取单位块，直到不能再取为止，得到的结果就是最优解。

如何选择最优的贪心标准以得到全局最优/较优解？

答：在排队问题中，人们排队到水龙头去打水，他们装满水桶的时间为T1、T2、…、Tn。为了使总花费时间最少，可以按照打水时间从小到大的顺序进 行排队。这是通过脑中模拟反证得出的结论，打水时间少的人应该排在最前面，以减少等待时间。

注意

最后，对于一个思路，无论它看起来多么合理，一定要设想其他方案并进行反证。这样可以确保贪心策略的有效性。

总的来说，贪心算法是一种简单而有效的求解最优化问题的方法，但并不适用于所有情况。选择正确的贪心标准非常重要，需要根据具体问题的需求来确定。

其他题目

仅供参考

// NOI Online 19
/*
在某次膜拜大会上, n 个神牛被要求集体膜拜
这些神牛被奖励每人吃一些神牛果
但是，每个神牛的肚量不一样
为了不显得某些人吃得太多
决定两人一组, 使得吃得最多的那组吃得尽量少
输入:
第一行: 一个偶数n (n <= 10000)
第二行: 为给定的一列数字, 长度为 n, 表示每个神牛能吃多少神牛果
输出:
一个正整数, 吃的最多的一组神牛吃的个数的最小值
*/
// Cate: Greedy
// Level: Low
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> l;
    vector<int> s;
    l.resize(n);
    for(int &i:l) cin >> i;
    for(int i = 0, j = n - 1;i <= n/2 - 1;i++, j--){
        s.push_back(l[i] + l[j]);
    }
    sort(s.begin(), s.end());
    cout << s.at(int(s.size() - 1)) << endl;
    return 0;
}