The Knapsack Problem is a well known problem of combinatorial optimization. Given a set of items, each with a weight and a value, we must determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value must be maximized.
The name of the problem comes from the problem faced by someone who is constrained by a fixed-size knapsack and must fit it with the most valuable items.
In that tutorial, you are going to solve the Knapsack Problem in Java on Eclipse by following a Dynamic Programming approach.
Note that you can also watch this tutorial in video on YouTube :
Designing an Item
First, we start by designing an Item for the Knapsack Problem. An Item will have the following properties :
- name helping us to identify it
- weight representing the weight of the item
- value representing the value of the item
We add also a str method returning a String representation of an Item. It gives us the following code :
Representing a Solution
Once the Knapsack problem will be solved, we will need a class to represent the solution. We will store the max value we can reach and also the items to include in the bag to maximize the value.
So, a Solution object will have the following properties :
- value storing the maximal value we can reach
- items’ list storing the Item objects to put in the bag to maximize the value and solve the Knapsack Problem
We add also a display method to print the solution on the screen. It gives us the following code :
Solving the Knapsack Problem
To solve the Knapsack Problem, we are going to implement a Dynamic Programming Algorithm. Like presented on Wikipedia, this algorithm can be expressed like that in pseudo code :
2 // Values (stored in array v)
3 // Weights (stored in array w)
4 // Number of distinct items (n)
5 // Knapsack capacity (W)
6 // NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.
8 for j from 0 to W do:
9 m[0, j] := 0
11 for i from 1 to n do:
12 for j from 0 to W do:
13 if w[i] > j then:
14 m[i, j] := m[i-1, j]
16 m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
Thus, in the matrix m, the m[i,w] value will be the maximum value that can be attained with weight less than or equal to w using items up to i (first i items).
It gives us the following Java code to implement this algorithm :
At the end of our Dynamic Programming Algorithm, the max value can be found in the matrix at the cell matrix[NB_ITEMS][capacity].
Finding the items to include in the bag
Next step is to find the items to include in the bag to maximize the value. Either the result comes from the top matrix[i-1][capacity] cell or from values[i-1] + weights[i-1][capacity-weights[i-1]] as in the matrix built previously.
It it comes latter one, it means the item is included in the bag to maximize the value. It gives us the following code to find the items to include :
Assembling all the pieces
At the end of the solve method, we return a Solution object containing the maximize value and the items’ list to include in the bag. We add also a display method in the Knapsack object to print on the screen the initial Knapsack Problem.
Finally, we add a main entry point and we assemble all the pieces to create a Knapsack problem, display it on the screen, solving it and then displaying the solution.
It gives us the following code for the Knapsack class :
Our Solver in Action
Last step is to put our Knapsack Problem solver in action. We consider the following instance of the Knapsack Problem :
- A bag with a capacity of 15kg
- 5 items to pick with values and weights defined
We run our Knapsack Problem solver with this instance. At the end of the execution, the solution is displayed in the console :
So, the value is maximized to 15 by including the elements 2, 3, 4 and 5 in the bag.
That’s all for that tutorial !
To discover more tutorials on Java development, you can subscribe to the SSaurel’s Channel :
This channel will offer you tutorials on Android, Web Development and some others programming tips. Some tutorials and…
If you want to discover some books to learn Java programming, I advice you to read the following article with my selection of the Top 6 Best Books for Java programming :