- 贪心：把整体问题分解成多个步骤，在每个步骤都选取当前步骤的最优方案，直至所有步骤结束；每个步骤不会影响后续步骤
- 核心性质：每次采用局部最优，最终结果就是全局最优
- 如果题目满足上述核心性质，则可以采用贪心进行求解
如何判断是否能用贪心？
- 最优子结构性质：当一个问题的最优解包含子问题的最优解，则称之为具有最优子结构性质。
- 贪心性质选择：可以通过局部最优的选择得到全局最优
具体问题如何做？
- 经验性积累各种类型的贪心
- 举反例
石子合并问题
石子合并问题：每次选择最小的两个
利用堆：
题目描述
在很久很久以前，有 个部落居住在平原上，依次编号为 到 。第 个部落的人数为 。
有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒，他能通过谈判来说服部落进行联合。
每次谈判，小蓝只能邀请两个部落参加，花费的金币数量为两个部落的人数之和，谈判的效果是两个部落联合成一个部落（人数为原来两个部落的人数之和）。
输入描述
输入的第一行包含一个整数 ，表示部落的数量。
第二行包含 个正整数，依次表示每个部落的人数。
其中，。
输出描述
输出一个整数，表示最小花费。
分箱问题
每组最多两件，价值之和不超过
尽可能不浪费空间：大的和小的凑在一起
题目描述
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入描述
第 行包括一个整数 ，为每组纪念品价格之和的上限。
第 行为一个整数 ，表示购来的纪念品的总件数。
第 ~ 行每行包含一个正整数 ，表示所对应纪念品的价格。
输出描述
输出一行，包含一个整数，即最少的分组数目。
GPT plus 代充 只需 145
翻硬币问题
题目描述
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 表示正面，用 表示反面（是小写字母，不是零）。
比如，可能情形是：;
如果同时翻转左边的两个硬币，则变为：。
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入描述
两行等长的字符串，分别表示初始状态和要达到的目标状态。
每行的长度<1000。
输出描述
一个整数，表示最小操作步数。
数组乘积问题
给定两个长度为 的正整数数组 和 ，可以任意排序，求 的最小值
思路： 从小到大， 从大到小，然后对应元素相乘结果最小
参考个人博客：贪心
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/242229.html