近似算法有哪些,举例说明什么是最优算法( 三 )

我们来看一个示例：项是 0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6，箱子的大小均为 1 。

文章插图
基于最先匹配法的装箱解决方案（M = 箱子总数 = 5）。
3. 最优匹配法 (Best Fit)：按顺序浏览箱子，将每一个新的项放在最适合的箱子里。如果不适合，则创建一个新的箱子。
我们来看一个示例：项是 0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6，箱子的大小均为 1 。

文章插图
基于最优匹配法的装箱解决方案（M = 箱子总数 = 5）。
该方法的输出与最先匹配法相同，但该方法的优点是实现速度比 FFD 快，即时间复杂度为 O(nlogn) 。
自然方法：
如果我们提前知道所有项的大小，那么自然的解决方案就是首先按照从大到小排序，然后应用以下启发式方法：
最先匹配递减法
最优匹配递减法
假设有相同的示例 0.7, 0.6, 0.5, 0.5, 0.5, 0.4, 0.2, 0.2, 0.1，则排序为 0.7, 0.6, 0.5, 0.5, 0.5, 0.4, 0.2, 0.2, 0.1 。

文章插图
优化方法（M = 箱子总数 = 4）。
参考文献：
1. https://cutt.ly/4hSDx2Y
2. https://cutt.ly/xhSDhEM
3. https://shorturl.at/hxCO5
4.***/wiki/Bin_packing_problem#Approximation_algorithms_for_bin_packing
5. ***/wiki/Partition_problem
6.***/daa-approximate-algorithms#:~:text=An%20Approximate%20Algorithm%20is%20a,at%20the%20most%20polynomial%20time
【近似算法有哪些,举例说明什么是最优算法】原文链接：***/aryan-gupta18/how-to-decide-suitability-of-approximation-algorithms-d8e45b90e530

近似算法有哪些,举例说明什么是最优算法( 三 )

推荐阅读

关于节约粮食的名言诗句关于节约粮食的名言和诗句

奋斗励志朋友圈句子励志短句致自己奋斗朋友圈

想发朋友圈表示心情不好的句子心情不好发朋友圈的句子心情短句

贝拉玻尿酸是合法的吗贝拉玻尿酸是进口的还是国产的

核桃仁做菜的菜谱，您知道桃仁脆溜鸡的做法

浅紫色显皮肤黑还是白

库伦旗景点

居家隔离和集中隔离的区别什么情况下要隔离28天

蝉蛹是什么

怎样能丰胸最安全有效