为什么贪心启发式不能给出文件存储的最优解决方案？

Question

为什么贪心启发式不能给出文件存储的最优解决方案？

我正在解决一个问题，我需要在硬盘上存储大小为 $f_1、f_2、\ldots、f_n$$ 的 $n$ 个文件。磁盘被分为多个段，每个段的大小为 ( K )。该问题有以下限制：

• 每个文件$f_i$必须小于或等于$K$
• 至少有 $n$ 个可用段。
• 文件不能分段，必须完全适合一个片段。
• 目标是尽量减少用于存储所有文件的段数量。

例如，当 $K = 1$ 且文件大小为 ( 0.2, 0.3, 0.6, 0.3, ) 和 ( 0.5 ) 时，最佳解决方案是使用两个段。您可以将 ( 0.6 ) 和 ( 0.3 ) 文件放在一个段中，并将其余文件放在另一段中。

该问题还提供了贪婪启发式：

1. 按大小降序对文件进行排序。
2. 对于每个文件，将其放置在仍能容纳该文件的最小剩余空间的段中。

我陷入了问题的 (b) 部分，要求我提供一个 ( K = 2 ) 的示例，其中这种贪婪的启发式方法无法产生最佳解决方案。我尝试过不同的文件大小，无论大小，但贪婪方法通常看起来效果很好。我无法找出失败的例子。

如有任何建议或澄清，我们将不胜感激！

Answer 1

K=2 时大小为 [.8, .8, .6, .6, .6, .6] 的文件需要 2 个段来进行最佳存储，但贪婪算法使用 3 个段。