目录
朴素的贪心法(上)最优化策略
常见贪心法归类
何为“朴素”贪心
最优化策略:取石子
取石子(改)
最优化策略适用条件
最优化策略:分析步骤
例题:机器工厂(USACO)
步骤1:划分阶段和决策
步骤2:验证最优子结构/无后效性
步骤2.5:修改决策
步骤2.5:重新验证最优子结构/无后效性
步骤3:最优化策略
步骤3:最优化策略(改进)
代码:机器工厂(C++)
1.最优化策略——每一次都采用当前最优决策
2.构造法——通过总结和归纳找到规律,直接推导出答案
3.二分答案——通过答案反推,验证合法性从而确定最优解
每次都选取最大~
由于条件限制,不能做到每次都拿最多,如果第一次拿3,第二次拿4时,第三次就不能再拿了
不适用贪心,但动态规划可解
第一,有明确的阶段,且每个阶段的决策都很清晰
第二,一个阶段的局部最优解,一定是从前面阶段的局部最优解得到的,这个特性称之为最优子结构
第三,后面阶段的决策,不会影响到前面阶段的决策,这个特性称为无后效性
1.划分问题的阶段和决策
2.验证最优子结构和无后效性
3.通过比较和判断,确定每一步的最优策略
局部最优解定义:完成前 K周订单的总成本最小(K=N)时就是全局最优解 在这个定义下,局部最优解一定是刚好满足K周订单需求即可不会额外生产供以后交付,否则会浪费
不满足最优子结构?
例:前三周每个机器生产成本分别是1,5,6,储藏成本是2
第三周要交付的机器如果在当周生产,成本是6,如果要在第二周生产,成本是5+2x1=7;如果要在第一周生产,成本是1+2x2=5
所以,第三周交付的机器,在第一周生产最省钱
虽然问题解决了,但是这个方法的效率还有提升空间
决策时,选择某一成本最低的一周的时候,我们刚刚采用的策略是挨个计算出每一周的成本,从而选择最小的,涉及了很多重复计算,成本的变化是有一定规律的,并不需要每次都进行计算~
直接把时间复杂度降低了一个数量级~时间复杂度对O(n)
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;