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;
}

{
if (CanFit(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.
{
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)
{
{
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))
{
foundSpace = true;
break;
}
}

if (!foundSpace)
{
{
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.
{
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()
};