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:
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!
Files of size [.8, .8, .6, .6, .6, .6] with K=2 take 2 segments to store optimally, but the greedy algorithm uses 3.