Knapsack Algorithm In C# .NET

I skipped out on University/College in my earlier years and instead opted to fully self teach myself programming. While that means I can chew someone’s ear off about the latest feature in C# 8, it also means that I missed out on plenty of “Data Structure/Algorithm” style programming problems. Let’s be honest, unless you are going for a job interview it’s rare you use these anyway – especially in programming business systems. But every now and again I come across an algorithm that I think “How have I not heard of this before?”. One such algo is the “Knapsack Problem”, also sometimes known as the “Rucksack Problem”.

One of the biggest issues I found with looking for an algorithm in C# to do this, is very rarely did they ever explain how the code worked, or even a thorough explanation on how to use it. So this is that explanation.

What Is The Knapsack Problem?

The Knapsack Problem is where you have a “bag” that can hold a limited number of items, given that you have a set of items to choose from each with individual “values”, how can you maximize filling your bag with only the most valuable items.

Let’s take a real world example. A robber has broken into a jewellery store and wants to steal precious jewellery. His backpack can only hold 50KG of weight (He’s superman). When he walks around the store thinking about what to steal, he has to do a sort of “cost/benefit” sum in his head to maximize his total take. As an example, with a 50KG bag, is it better to steal a 50KG item worth $100, or steal five 10kg items worth $50 each? Obviously the latter because even though that one item is more valuable, it takes up all the space in the bag, whereas stealing multiple smaller items actually maximizes the value the bag can hold. This is the knapsack/rucksack problem.

Code Explanation

Before I just give you the code, I want to explain a little bit first on how this actually works. Even though the code below has a tonne of comments, I still want to go that extra mile because it can be hard to wrap your head around at first.

The code works a bit like this :

• Create a loop to go through each jewel one by one.
• Given a smaller bag, and increasing the bag size each loop, check if the jewel can fit inside the bag (Even if we had to empty out something else)
• If the Jewel can fit, then work out what’s already in the “bag” by checking what the last value was when we looped at this bag size. Or another way of putting it, on the last jewel we looped on, when we were at this weight, what was the value? And with the current jewel we have, it we combine it with other jewels to make up the other space in the bag, who has the higher value? If it’s the current Jewel + extra then set a matrix value to that, otherwise set it to the last jewel we fit at this weight.
• If the jewel can’t fit into our smaller bag (e.g.  The jewel weighs 30KG but our bag can only carry 20KG, then take whatever the last jewel round was that fit into this 20KG bag).
• As we carry values forward, then at the very end, the last indexes in our matrix will be the maximum value.

… I’m going to stop here and say that this is probably a little confusing. So let’s take an example of where we might be in the current loop cycle and how this might look by building a quick flow diagram. (Click to open to a larger image).

Knapsack Code

Now here’s the code. Note that this is not crazy optimized with one letter variables names for a leetcode competition, but it’s written in a way that hopefully is easier to understand.

public class Jewel
{
	public int Weight { get; set; }
	public int Value { get; set; }
}

public static int KnapSack(int bagCapacity, List jewels)
{
	var itemCount = jewels.Count;

	int[,] matrix = new int[itemCount + 1, bagCapacity + 1];

	//Go through each item. 
	for (int i = 0; i <= itemCount; i++)
	{
		//This loop basically starts at 0, and slowly gets bigger. 
		//Think of it like working out the best way to fit into smaller bags and then keep building on that. 
		for (int w = 0; w <= bagCapacity; w++)
		{
			//If we are on the first loop, then set our starting matrix value to 0. 
			if (i == 0 || w == 0)
			{
				matrix[i, w] = 0;
				continue;
			}

			//Because indexes start at 0, 
			//it's easier to read if we do this here so we don't think that we are reading the "previous" element etc. 
			var currentJewelIndex = i - 1;
			var currentJewel = jewels[currentJewelIndex];
			//Is the weight of the current jewel less than W 
			//(e.g. We could find a place to put it in the bag if we had to, even if we emptied something else?)
			if (currentJewel.Weight <= w)
			{
				//If I took this jewel right now, and combined it with other gems
				//Would that be bigger than what you currently think is the best effort now? 
				//In other words, if W is 50, and I weigh 30. If I joined up with another jewel that was 20 (Or multiple that weigh 20, or none)
				//Would I be better off with that combination than what you have right now?
				//If not, then just set the value to be whatever happened with the last item 
				//(may have fit, may have done the same thing and not fit and got the previous etc). 
				matrix[i, w] = Math.Max(currentJewel.Value + matrix[i - 1, w - currentJewel.Weight]
										, matrix[i - 1, w]);
			}
			//This jewel can't fit, so bring forward what the last value was because that's still the "best" fit we have. 
			else
				matrix[i, w] = matrix[i - 1, w];
		}
	}

	//Because we carry everything forward, the very last item on both indexes is our max val
	return matrix[itemCount, bagCapacity];
}

static void Main(string[] args)
{
	var items = new List
		{
			new Jewel {Value = 120, Weight = 10},
			new Jewel {Value = 100, Weight = 20},
			new Jewel {Value = 500, Weight = 30},

		};

	Console.WriteLine(KnapSack(50, items));
}

I’ve included a sample little console debug (So you can paste this into a new console app), to illustrate how it works. Again, I’ve commented and used a “Jewel” class to illustrate the example a little more so that hopefully it’s easier to understand than some code golf example. Even if you don’t use C# as your main language, hopefully it’s easy to follow!