贪心算法

需要证明问题具有贪心选择性质和最优子结构。为了保证正确性，我们应该对贪心策略进行严谨的数学证明，通常需要用到反证法或数学归纳法。

解决的问题

• 硬币找零问题：在某些硬币组合下，贪心算法总是可以得到最优解。
• 区间调度问题：假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务，那么贪心算法就可以得到最优解。
• 分数背包问题：给定一组物品和一个载重量，你的目标是选择一组物品，使得总重量不超过载重量，且总价值最大。如果每次都选择性价比最高（价值 / 重量）的物品，那么贪心算法在一些情况下可以得到最优解。
• 股票买卖问题：给定一组股票的历史价格，你可以进行多次买卖，但如果你已经持有股票，那么在卖出之前不能再买，目标是获取最大利润。
• 霍夫曼编码：霍夫曼编码是一种用于无损数据压缩的贪心算法。通过构建霍夫曼树，每次选择出现频率最小的两个节点合并，最后得到的霍夫曼树的带权路径长度（即编码长度）最小。
• Dijkstra 算法：它是一种解决给定源顶点到其余各顶点的最短路径问题的贪心算法。
• 最大容量问题: 放置两个隔板
• 最大切分乘积问题: 给定一个正整数 n ，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少。