greedyheuristics

Why doesn't the greedy heuristic give the optimal solution for file storage?


Why doesn't the greedy heuristic give the optimal solution for file storage?

I'm working on a problem where I need to store $n$ files of sizes $f_1, f_2, \ldots, f_n$$ on a hard disk. The disk is divided into segments, each of size ( K ). The problem has the following constraints:

For example, when $K = 1$ and the file sizes are ( 0.2, 0.3, 0.6, 0.3, ) and ( 0.5 ), the optimal solution is to use two segments. You can place the ( 0.6 ) and ( 0.3 ) files in one segment and the remaining files in another.

The problem also provides a greedy heuristic:

  1. Sort the files in decreasing order of size.
  2. For each file, place it in the segment with the smallest remaining space that can still fit the file.

I'm stuck on part (b) of the problem, where I'm asked to provide an example with ( K = 2 ) where this greedy heuristic does not yield the optimal solution. I’ve tried different file sizes, large and small, but the greedy method often seems to work fine. I can’t figure out an example where it fails.

Any suggestions or clarifications would be appreciated!


Solution

  • Files of size [.8, .8, .6, .6, .6, .6] with K=2 take 2 segments to store optimally, but the greedy algorithm uses 3.