贪心算法【自用】
顾名思义，该算法一次构建一个解决方案，然后选择下一个提供最明显和直接好处的部分，即，这是当时最优化的选择。因此，选择局部最优也会导致全局解的问题最适合 Greedy。
贪心算法的一些重要问题是：
| 算法 | 描述 |
|---|---|
| 部分背包 | 查找可以放入背包中的物品的最大总价值，允许部分包含物品。 |
| Dijkstra 算法 | 查找从源顶点到加权图中所有其他顶点的最短路径。 |
| Kruskal 算法 | 查找加权图的最小跨度树。 |
| 哈夫曼编码 | 为一组符号创建最佳前缀代码，从而最小化总编码长度。 |
相关文章：
| 经典问题 | 贪心算法 | Link |
|---|---|---|
| 0-1 背包问题 | ❌ | |
| 部分背包问题 | ✅ | 部分背包【图文】 |
| 旅行售货员问题 | ❌ | |
| 最长公共子序列 | ❌ | |
| 最小生成树 | ✅ (Kruskal, Prim) | VisuAlgo - Minimum Spanning Tree【动画】 |
| 单源最短路径 | ✅ (Dijkstra) | VisuAlgo - Single-Source Shortest Paths【动画】 |
| 八皇后问题 | ❌ | |
| 装载问题 | ❌ | |
| 批处理作业调度 | ❌ | |
| 最大团问题 | ❌ | |
| 装箱问题 | ✅ | Greedy Algorithm Bin Packing Problem |