朴素的贪心法(上)最优化策略
常见贪心法归类
1.最优化策略——每一次都采用当前最优决策
2.构造法——通过总结和归纳找到规律，直接推导出答案
3.二分答案——通过答案反推，验证合法性从而确定最优解
何为“朴素”贪心
- 所谓“朴素”，就是可以通过确定性的贪心步骤得出最优解
- 有些问题很难通过确定性贪心步骤得到最优解，但可以通过在贪心时加入随机因素(不是每次都选最优策略，而是几种较好策略中随机选择一种)，来得到近似最优解
- 当随机次数足够多时，这个近似最优解就会无限逼近最优解这个方法称为随机贪心法，后续会
最优化策略:取石子
每次都选取最大~ 
取石子(改)
由于条件限制，不能做到每次都拿最多，如果第一次拿3，第二次拿4时，第三次就不能再拿了 
不适用贪心，但动态规划可解
最优化策略适用条件
第一，有明确的阶段，且每个阶段的决策都很清晰
- 阶段一定是按顺序执行的
- 对于第K(1≤K≤N)个阶段，前K轮的最优决策集合称为局部最优解当K=N时，称为全局最优解
第二，一个阶段的局部最优解，一定是从前面阶段的局部最优解得到的，这个特性称之为最优子结构
- 例:取石子里，第二轮如果取4，那么无论第三轮取什么，总数一定不是最多。只有第二轮取5(局部最优解)第三轮才有可能产生总数最多的情况
- 反例:取石子(改)里，第二轮取5是当前最优，但第三轮取4是最优。只有第二轮不取当前最优时，第三轮才能取到最优——不适用贪心法
第三，后面阶段的决策，不会影响到前面阶段的决策，这个特性称为无后效性
- 例:无论第二轮取哪一堆，都不影响第一轮取的石子
- 反例:题目修改为“每种数目的石子只能取一次，比如这一次取了5个，下一次就不能再取5个”——后面选择跟前面冲突的话，就需要返回修改之前的选择
最优化策略:分析步骤
1.划分问题的阶段和决策
2.验证最优子结构和无后效性
3.通过比较和判断，确定每一步的最优策略
例题:机器工厂(USACO) 
步骤1:划分阶段和决策
- 阶段:周数 K(1 ≤K≤ N)
- 决策:第 K周生产多少台机器
步骤2:验证最优子结构/无后效性
- 无后效性:满足
- 因为第 K 周生产几台都不影响第1~K-1周的交付(不可能后面生产的穿越回去交付前面的订单)
- 最优子结构呢?
局部最优解定义:完成前 K周订单的总成本最小(K=N)时就是全局最优解 在这个定义下，局部最优解一定是刚好满足K周订单需求即可不会额外生产供以后交付，否则会浪费 
不满足最优子结构? 
步骤2.5:修改决策
- 问题出在决策:不能只满足本周的需求而不考虑后续需要
- 反向思考1:本周要交付的机器可以是本周生产，也可以是之前生产
- 反向思考2:不管前面是哪周生产，成本都可以直接算出来(等于该周生产成本+储藏成本x周数差)
例:前三周每个机器生产成本分别是1，5，6，储藏成本是2
第三周要交付的机器如果在当周生产，成本是6，如果要在第二周生产，成本是5+2x1=7;如果要在第一周生产，成本是1+2x2=5
所以，第三周交付的机器，在第一周生产最省钱
步骤2.5:重新验证最优子结构/无后效性
- 决策修改为:第K周要交付的机器应该在第几周生产
- 无后效性仍然满足
- 最优子结构也满足:前K周总成本最低的情况，一定是从前K-1周总成本最低的情况推出来的
步骤3:最优化策略
- 对于第K周，计算本周交付的机器在第i(1≤i≤K)周生产并储藏到第K周，分别所需要的成本
- 选择成本最低的一周，由它来生产第K周需要交付的订单
- 将这个最低的成本加上前K-1周的最低总成本，得到前K周的最低总成本(局部最优解)。K=N时得到的就是最终答案
虽然问题解决了，但是这个方法的效率还有提升空间
决策时，选择某一成本最低的一周的时候，我们刚刚采用的策略是挨个计算出每一周的成本，从而选择最小的，涉及了很多重复计算，成本的变化是有一定规律的，并不需要每次都进行计算~
步骤3:最优化策略(改进) 
直接把时间复杂度降低了一个数量级~时间复杂度对O（n）
代码:机器工厂（C++）
int n, s; // 声明变量n和s，分别表示总共的星期数和保养一台机器的费用 cin >> n >> s; // 输入总星期数和保养费用 int p, y, min_p = INT_MAX - s; // 声明变量p、y和min_p，min_p初始化为INT_MAX-s，用来存放当前最小的生产成本 long long total = 0; // 声明变量total用来存放总花费 for (int i = 0 ;i < n; i++) // 循环n次，表示n个星期 { cin >> p >> y; // 输入当前星期生产一台机器的成本p和订单数量y min_p = min(min_p + s, p); // 对当前最小成本进行更新，考虑了保养费用 total += min_p * y; // 计算当前星期的总花费，加上当前最小成本乘以订单数量 } cout << total << endl; // 输出总花费 return 0;
希望对你有帮助！加油！
若您认为本文内容有益，请不吝赐予赞同并订阅，以便持续接收有价值的信息。衷心感谢您的关注和支持！
