In our previous article, we touched on the Travelling Salesman problem and highlighted how it belongs to the subfield of combinatorial optimisation. The topic of combinatorial optimisation seeks to discover the most efficient object from a finite set of items.  The three main combinatorial optimisation problems are Travelling Salesman Problem (TSP), Knapsack problem and Minimum Spanning Tree (MST). Our focus will be on the Knapsack problem in this article. A subsequent piece will touch on MST. 

Diving  into the Knapsack Problem

Let’s now assume a deeper look into the logic of the Knapsack Problem. The decision version of the Knapsack problem is considered NP-Complete. Firstly, we will briefly examine the problem statement. Providing a set of objects with attributable value and weights (Vi, Wi), what is the maximum value that can be attained when the sum of the subsets of these objects are selected to be within the knapsack capacity. In a  simpler manner, using the image below, the maximum capacity of the knapsack is 40kg and we have a variety of items with their respective values and weights. The idea is to pick enough items whose total will be less than 40kg with special consideration to the value. In essence, we want to add as many items that will cost us the least. It is similar to going shopping and you are not able to get all the items you desired to get because there is no carrier bag and all you have is a laptop backpack. The number of items you can purchase in this context will be limited to the capacity of your bag.

Continue reading →