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.
After selecting the appropriate items that can fit into your knapsack, you can then check your receipt to determine the overall value of the items. This grocery shopping experience is quite similar to the knapsack problem. The data that is inputted in the matrix of the Knapsack problem is the actual value (i.e price from the image above), The weight of the individual items are used to determine compatibility during the compute stage and the respective value is entered for the relevant items. We will look at a matrix representation of a knapsack problem scenario.
Matrix representation of the knapsack problem
We will represent the matrix of a knapsack problem below. More simply, we will use a different knapsack example with a maximum capacity of 8kg.
Each row of the above matrix represents an object or item for which there is a relevant value and weight. The column symbolises the sequential capacity of the knapsack to a maximum of 8. The idea is to input the relevant values at each interjection between the columns and the rows. The maximum capacity of the knapsack is realised in cells containing 8kg. As earlier stated, the weights and the relevant value of the object determines its suitability to be added to the knapsack. It is a combinatorial optimisation problem geared at discovering the optimal choice of objects.
The implementation of the knapsack problem in Python