When I wrote a post about an idea I had at a bank about making change from $5 and $8, a reader wrote me that this was the knapsack problem. I decided to research it. I discovered that although my post was not a knapsack problem, it was somewhat similar because it involved resource optimization. So, intrigued by the knapsack problem, I decided to write code on the 0/1 knapsack problem.
What is the 0/1 knapsack problem?
The knapsack problem was stated using a burglar and how difficult it is being a burglar especially when you are greedy. Imagine a burglar breaks into a home carrying a knapsack with a fixed capacity. What he can steal is limited by the capacity of the knapsack. But the problem is that the items in the home have more value than what his knapsack can carry. So, he has a decision problem. What would he decide to take that would fit into his knapsack? In this problem, he cannot take pieces of items but he either chooses to take the item completely or leaves it (that is why it is called the 0/1 knapsack problem). How does the burglar decide on what to choose?
Let’s take an example of the items the burglar might find in the home. For example, the items he might need to choose from might be a clock, painting, radio, vase, book and computer with values and weight like in the table below:
| Name | Value | Weight | Value/Weight ratio |
|---|---|---|---|
| Clock | 175 | 10 | 17.5 |
| Painting | 90 | 9 | 10 |
| Radio | 20 | 4 | 5 |
| Vase | 50 | 2 | 25 |
| Book | 10 | 1 | 10 |
| Computer | 200 | 20 | 10 |
Which items would he decide to take? We are going to analyze what options the burglar can make.
Why being greedy might not be optimal here.
The burglar has three dimensions of greed in making a choice. He would choose the best item first, then the next best, and so on until he reaches the limit of his knapsack. But what would best mean for him? Could it mean the most valuable, the least weight, or the highest value/weight ratio? Let’s give a value to the capacity of his knapsack and say he can only take items up to 20 kg. So, given a knapsack of 20 kgs, what combination of items can he take?
A stupid burglar or one in a hurry would just pick the computer and say that would give him the best value. But that is not the case. An intelligent burglar would go through his value system and decide what is best for him. But he doesn’t have all the time in the world. So, on the spur he chooses what is best based on his greed and picks accordingly. He has three dimensions of greed to choose from: based on value, based on least weight, and based on the density or value to weight ratio of the items.
I have written here a little code based on the greedy algorithm. It is named my_greed.py.To make the decision, the burglar would have to sort the items ranking them in order and picking each item until he exhausts his knapsack. You can download the code and run it on your machine and test it to see the solutions he would get for his greed.
If you run it you would get the following results. Based on values, if he picks the clock, radio and book, he would steal items that are worth 275. If he decides based on weight, he would pick the book, vase, radio and painting which are all worth 170. If he decides based on density or value to weight ratio, he would pick the vase, clock, book and radio which are all worth 255. So, the best solution for the burglar on the spur is to pick based on value where he gets a total value of 275. Unfortunately, because of greed, some burglar would just pick the computer which is only worth 200.
But choosing based on greed is not always the optimal solution. The burglar wouldn’t be able to consider all the possibilities of his choice. So, that is why I am not explaining the code for greed on this post. You need to study it to understand it yourself. I want to dwell on using the optimal solution.
The optimized algorithm for the knapsack problem.
I thought carefully about this problem and decided that the best and optimal solution for the burglar is to do the following (but he wouldn’t have all the time in the world):
1. Enumerate all the possible combination of items.
2. Remove all the combinations whose weight exceeds the capacity of the knapsack.
3. From the remaining combinations, choose any whose value is the highest.
So that is the focus of this blog. Using an optimal algorithm in getting a solution to the 0/1 knapsack problem. We will go through all the steps above one after the other using code. I hope you ride along.
First, we need to create the class for the items.
# create the items class
class Items(object):
def __init__(self, name, value, weight):
self.name = name
self.value = value
self.weight = weight
def get_name(self):
return self.name
def get_value(self):
return self.value
def get_weight(self):
return self.weight
def __str__(self):
result = f'{self.name}: Value = {self.value}.
Weight = {self.weight}.'
return result
In the constructor, each item instance has a name, value and weight. Then there are the getters for the attributes. Then the last method is the __str__() method that specifies how to represent each object on the output.
Then the next thing to do is to build the Items into a list. With the list of items, we can create a superset later.
# build the items in a list
def build_items():
names_list = ['Clock', 'Painting', 'Radio', 'Vase',
'Book', 'Computer']
values_list = [175, 90, 20, 50, 10, 20]
weight_list = [10, 9, 4, 2, 1, 20]
collection = []
for i in range(len(names_list)):
collection.append(Items(names_list[i], values_list[i],
weight_list[i]))
return collection
I created a separate list for each attribute and then in the for loop I created each item instance with their data. Then returned the list, collection.
Now that we have all data items in a list, we now need to enumerate all possible combinations of the items.
# create the powerset
from itertools import combinations, chain
def powerset(iterable):
s = list(iterable)
# powerset removes the empty set
return list(chain.from_iterable(combinations(s, r)
for r in range(1, len(s)+1)))
Notice that I imported the combinations and chain methods from itertools to create the powerset. It’s very easy. If you want an explanation of what was involved in creating the powerset, just read this blog post on combinations.
Then the last two activities to do is to remove all combinations whose total weight exceeds the capacity of the knapsack. When we have done that, from the remaining combinations, find out which of them gives us the maximum value because now all the remaining combinations can fit into the knapsack. This code does both activities.
# the main code
def choose_best(pset, max_weight):
best_val = 0.0
best_set = None
for items in pset:
items_val = 0.0
items_weight = 0.0
for item in items:
items_val += item.get_value()
items_weight += item.get_weight()
if items_weight <= max_weight and items_val > best_val:
best_val = items_val
best_set = items
return (best_set, best_val)
Now let me explain the code a little. The arguments to the choose_best method are powerset and max_weight, which is the weight of the sack. I then initialized best_val to capture the highest value among the combinations and best_set, to capture the best combination. Then in the outer for loop, I initialized the variables items_val and items_weight which are used as total values and total weights for each combination. Then in the inner for loop I iterate through each of the items in any chosen combination, getting their total value and total weight. Then, what I did next is check for whether the total weight, items_weight, is less than or equal to sack weight, the max_weight, and also if the total value, items_val, is greater than any other total value in previous combinations, if both cases are true, then it sets the total value, items_val, as the best value, best_val and tags this combination of items, best_set as the chosen combination. It then returns the best value, best_val, and the chosen combination, best_set, as a tuple.
Now the code to test the main code.
# code to test
def test_best(max_weight=20):
items = build_items()
pset = powerset(items)
taken, val = choose_best(pset, max_weight)
print('Total value of items taken is', val)
for item in taken:
print(item)
Since the weight of the knapsack is 20 kg, I set the max_weight as default of 20. You can specify something else when you are running the code. Then in the body of the function I built the items or collect the items into a list, then create the powerset of all the items. After that, I called the choose_best method to make the optimal choice or solution. Then in the final part of the code I use a for loop to print out each of the items that were in the chosen combination.
Here now is the complete program so you can run it here.
If you desire to study it in-depth and also run it on your own terminal, here is the download file, my_items.py.
That’s it. It’s fun coding the 0/1 knapsack problem. I hope you enjoyed it. I did.
You can leave comments below. Also, subscribe to my blog so that you can receive latest updates.
Happy pythoning.
