Class DiskPacking

java.lang.Object
topics.greedy.disk.DiskPacking
public class DiskPacking extends Object

Disk Packing

Demonstrates two distinct greedy strategies for packing files onto a disk with limited capacity. Illustrates a critical concept in algorithm design: the same greedy paradigm can yield a mathematically optimal solution for one objective, but fail (act only as a heuristic) for another.

Author:
vicegd

  • Constructor Details

    • DiskPacking

      public DiskPacking()

  • Method Details

    • maximizeFileCount

      public int maximizeFileCount(int[] files, int discCapacity)

      Objective 1: Maximize Number of Files

      Greedy Strategy: Sort files ascending. Pick the smallest files first.
      Result: GUARANTEES the mathematically optimal maximum number of files.

      • Time Complexity: O(N log N) - Bound by sorting.
      • Space Complexity: O(N) - Defensive copy to prevent side-effects.
      Parameters:
      files - Array containing the sizes of available files.
      discCapacity - The maximum storage capacity of the disk.
      Returns:
      The maximum number of files that can be stored.

    • maximizeSpaceUsage

      public int maximizeSpaceUsage(int[] files, int discCapacity)

      Objective 2: Maximize Space Usage (Minimize Free Space)

      Greedy Strategy: Sort files descending. Pick the largest files that fit.
      Result: DOES NOT GUARANTEE the optimal solution. This is a heuristic (a fast approximation). Finding the absolute optimal configuration is a variant of the 0/1 Knapsack Problem, which requires Dynamic Programming O(N*W).

      • Time Complexity: O(N log N) - Bound by sorting.
      • Space Complexity: O(N) - Defensive copy.
      Parameters:
      files - Array containing the sizes of available files.
      discCapacity - The maximum storage capacity of the disk.
      Returns:
      The total amount of disk space utilized by the greedy heuristic.