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.

Continue reading →