Knapsack Packing

The knapsack problem came up the other day when I was thinking about how best to "defrag" a set of objects that are added and removed over time with the overall effect that one day the objects are scattered throughout an area when they could be rearranged to fit into a smaller area and save cost.

Box

class Box
{
    public string Id { get; set; }

    public int Size { get; set; }

    public override string ToString()
    {
        return $"{Id} {Size}";
    }

    public bool WillFitInto(Bin bin)
    {
        return this.Size <= bin.FreeSpace;
    }

    public static int CompareBySizeDescending(Box x, Box y)
    {
        return y.Size.CompareTo(x.Size);
    }
}

Bin

class Bin
{
    public static int BinSize = 4;

    public Bin()
    {
        this.Size = BinSize;
        this.Contents = new List<Box>();
    }

    public string Id { get; set; }

    public List<Box> Contents { get; set; }

    public int Size { get; set; }

    public override string ToString()
    {
        return $"{Id} {FreeSpace} of {Size}";
    }

    public bool CanFit(Box box)
    {
        return box.Size <= this.FreeSpace;
    }

    public void Add(Box box)
    {
        if (CanFit(box))
        {
            this.Contents.Add(box);
        }
    }
    
    public int AllocatedSpace
    {
        get
        {
            return this.Contents.Sum(s => s.Size);
        }
    }

    public int FreeSpace
    {
        get
        {
            return this.Size - this.AllocatedSpace;
        }
    }
}

Greed

After some reading up on the problem, I thought that the greedy approximation algorithm proposed by George Dantzig would do the job. This algorithm takes a list of the objects, sorted by decreasing order of "size", then tries to insert the largest object into the first container and continues with the next largest until there is no more room for that object (but there may be room for smaller objects).

We create a new container for the object that wouldn't fit into any of the other containers and add it there. Every time we try to fit an object, we start at the first container and test them all until we find a space, then continue with the next largest.

Setup

For our purposes, I have set each container or bin to have a fixed size. Each box is allocated a random size between 1 and the maximum size of the bin.

Random random = new Random();

var boxes = new List<Box>();

for (int i = 0; i < 800; ++i)
{
    // allocate a random size to each box.
    boxes.Add(new Box
    {
        Id = (i + 1).ToString(),
        Size = random.Next(1, Bin.BinSize + 1)
    });
}

int sizeOfAllBoxes = boxes.Sum(x => x.Size);
// since we are going to randomly assign them, let's make that 3 * as big as we need.
int originalRequiredBins = 3 * sizeOfAllBoxes;

var originalBins = new List<Bin>(originalRequiredBins);

for (int i = 0; i < originalRequiredBins; ++i)
{
    originalBins.Add(new Bin
    {
        Id = (i + 1).ToString()
    });
}

PrintStats(originalBins);

Statistics

For testing purposes we need a random ordering of the items to begin with some randomly assigned boxes and containers or bins with a calculable wastage score.

private static void PrintStats(IEnumerable<Bin> bins)
{
    foreach (var bin in bins)
    {
        Console.WriteLine();
        Console.WriteLine("Bin {0}", bin.Id);
        Console.WriteLine("--------");

        Console.WriteLine("Used {0} Free {1}", bin.AllocatedSpace, bin.FreeSpace);

        Console.WriteLine();

        foreach (var site in bin.Contents)
        {
            Console.WriteLine("\tBin {0} Size {1}", site.Id, site.Size);
        }
    }

    Console.WriteLine("{0} Bins", bins.Count());

    Console.WriteLine("Allocations:");
    int fullyAllocated = bins.Count(x => x.FreeSpace == 0);
    int partiallyAllocated = bins.Count(x => x.FreeSpace > 0 && x.AllocatedSpace > 0);
    int unallocated = bins.Count(x => x.AllocatedSpace == 0);
    Console.WriteLine("Fully {0} bins", fullyAllocated);
    Console.WriteLine("Partly {0} bins", partiallyAllocated);
    Console.WriteLine("Free {0} bins", unallocated);

    int boxes = bins.Sum(x => x.Contents.Count());

    Console.WriteLine("Wastage:");
    int waste = bins.Sum(x => x.FreeSpace);
    Console.WriteLine("{0} units", waste);
}

Setup

foreach (var box in boxes)
{
    Console.WriteLine("Fitting Box {0}", box);

    bool foundSpace = false;

    for (int attempt = 0; attempt < 10; ++attempt)
    {
        int binNumber = random.Next(originalBins.Count);
        var chosenBin = originalBins[binNumber];

        Console.WriteLine("Trying Bin {0}", chosenBin);

        if (chosenBin.CanFit(box))
        {
            Console.WriteLine("Adding to Bin");
            chosenBin.Add(box);
            foundSpace = true;
            break;
        }
    }

    if (!foundSpace)
    {
        originalBins.Add(new Bin
        {
            Id = originalBins.Count.ToString()
        });
    }
}

// now remove all that are completely empty...
originalBins.RemoveAll(x => x.AllocatedSpace == 0);

Since the random allocation may not fill up all the bins, we remove any completely empty bins so we don't skew the figures too much.

After testing the random allocation for a few samples, rough figures are about one quarter of the bins are fully allocated and the remaining three quarters are partially allocated and with wastage (empty space in bins) for 800 boxes measured in the low thousands.

Greedy

Running the greedy approximation algorithm, first sorting the list into decreasing sizes, we allocate to bins in order of fit and create new bins as appropriate.

boxes.Sort(Box.CompareBySizeDescending);

var defraggedBins = new List<Bin>();

int binCount = 1;

// add first bin, definitely will need.
defraggedBins.Add(new Bin 
{ 
    Id = binCount.ToString() 
});

foreach (var box in boxes)
{
    Bin firstAvailableBin = defraggedBins.FirstOrDefault(x => box.WillFitInto(x));

    if (firstAvailableBin == null)
    {
        // nothing big enough, add a new bin.
        binCount++;
        firstAvailableBin = new Bin 
                            { 
                                Id = binCount.ToString() 
                            };

        defraggedBins.Add(firstAvailableBin);
        Console.WriteLine("Adding new Bin {0}", firstAvailableBin);
    }

    firstAvailableBin.Add(box);
}

PrintStats(defraggedBins);

Results

After running the algorithm, the stats say that we save about 25-30% of bins and have wastage of zero or one bins and typically in single figures for wastage of free space units across all the bins.