# Building a Python Bot to Solve the Knapsack Problem

In this project, we will be building a Python bot to solve the Knapsack Problem. The Knapsack Problem is a classic optimization problem that involves selecting a subset of items, each with a weight and a value, in such a way that the total weight is less than or equal to a given limit and the total value is maximized. Our first bot will use a simple for loop to solve this problem and output the optimal subset of items to pack in the knapsack.

## Python Classes Needed for the Knapsack Problem

• Item
• `name`: a string representing the name of the item
• `mass`: a positive integer representing the weight of the item
• `price`: a positive integer representing the value of the item
• Knapsack
• `name`: a string representing the name of the knapsack
• `allowed_mass`: a positive integer representing the maximum weight that the knapsack can hold
• KnapsackPackage
• `name`: a string representing the name of the knapsack package
• `items`: a list of `Item` contained in the knapsack package
• `allowed_mass`: a positive integer representing the maximum weight that the knapsack can hold

The `Knapsack` class is typically used to represent the container or bag that can hold a subset of items with a total weight less than or equal to a given limit. It is possible that the `Knapsack` class also has additional methods that help to add, remove, or retrieve items from the knapsack.

The `KnapsackPackage` class represents a `Knapsack` that has been filled with several `Item`. In Python we can use the inheritance of classes.

In Python, we can define the inheritance of classes by creating a new class that inherits the properties and methods of an existing class. To do this, we use the name of the existing class in parentheses after the name of the new class.

For example, let's say we have a class called `Animal` with properties such as `name`, `species`, and `age`, as well as methods such as `eat` and `sleep`. We can define a new class called `Dog` that inherits these properties and methods by writing:

``````class Dog(Animal):
pass``````

The `pass` keyword here indicates that we are not adding any additional properties or methods to the `Dog` class. However, we can add new properties or methods by simply defining them within the `Dog` class:

``````class Dog(Animal):
def bark(self):
print("Woof!")``````

Now, the `Dog` class has all of the properties and methods of the `Animal` class, as well as a new method called `bark`.

When we create an instance of the `Dog` class, we can use all of the properties and methods of both the `Dog` and `Animal` classes:

``````my_dog = Dog("Fido", "dog", 3)
print(my_dog.name) # Output: Fido
print(my_dog.species) # Output: dog
print(my_dog.age) # Output: 3
my_dog.eat() # Output: Nom nom nom
my_dog.sleep() # Output: Zzzzzzzz
my_dog.bark() # Output: Woof!``````

This is the basic idea behind class inheritance in Python.

Going back to our knapsack problem, the `KnapsackPackage` class has all the properties of the `Knapsack` class, so the first one can inherit from the other.

To make the problem more interesting, additional parameters can be added to the different classes. For instance, the `Item` class can have a color attribute that is automatically filled depending on the price per kilogram. Let’s say that if the price per kilogram is:

• Less than 5€/kg, the color should be bronze.
• Between 5 and 15€/kg, the color should be silver.
• Over 15€/kg, the color should be gold.

This way, the `KnapsackPackage` will be able to count how many items of each color it contains. This count can now be a new parameter of the `KnapsackPackage` class and can be used in trade-offs for comparing different solutions. Moreover, the obvious parameters to add to the `KnapsackPackage` class are its total value and its total mass, which must not exceed the `allowed_mass`.

Here is what the Python code should look like if we follow the information listed above.

``````from dessia_common.core import PhysicalObject, DessiaObject
from typing import List``````
``````class Item(PhysicalObject):
_standalone_in_db = True

def __init__(self, mass: float, price: float, name: str):
self.mass = mass
self.price = price
PhysicalObject.__init__(self, name=name)

self.price_per_kg = price / mass
if self.price_per_kg <= 5:
self.color = 'bronze'
self.rgb = (97/255, 78/255, 26/255)  # Bronze color
elif 5 < self.price_per_kg < 15:
self.color = 'silver'
self.rgb = (192/255, 192/255, 192/255)  # Silver color
else:
self.color = 'gold'
self.rgb = (255/255, 215/255, 0/255)  # Gold color``````
``````class Knapsack(PhysicalObject):
_standalone_in_db = True

def __init__(self, allowed_mass: float, name: str):
self.allowed_mass = allowed_mass
PhysicalObject.__init__(self, name=name)``````
``````class KnapsackPackage(Knapsack):
_vector_features = ["mass", "price", "golds", "silvers", "bronzes"]
_standalone_in_db = True

def __init__(self, items: List[Item], allowed_mass: float, name: str):
self.items = items
Knapsack.__init__(self, allowed_mass=allowed_mass, name=name)

self.mass = sum(item.mass for item in items)
self.price = sum(item.price for item in items)
self.golds = 0
self.silvers = 0
self.bronzes = 0
for item in items:
if item.color == 'gold':
self.golds += 1
elif item.color == 'silver':
self.silvers += 1
elif item.color == 'bronze':
self.bronzes += 1``````

The inheritance from `DessiaObject` or `PhysicalObject` is mandatory for Dessia platform compatibility, as well as the special attributes `_standalone_in_db` and `_vector_features`. A detailed explanation is available in the chapter called Quick Start with Dessia SDK.

## Generating solutions

The last part consists in founding the best solution for the Knapsack Problem. In order to do so a generator of solutions is a powerful tool. The generator will be a Python class that takes for inputs an exhaustive list of `Item` and a `Knapsack`. The generator will then try all the combinations of items to found the best one, the one with the most value given the knapsack’s capacity.

To generate all the combination, we can use the inbuilt function named `combination` from the `itertools` library. Here is what the generator should look like.

``````from itertools import combination

class Generator(DessiaObject):
_standalone_in_db = True

def __init__(self, items: List[Item], knapsack: Knapsack):
self.items = items
self.knapsack = knapsack
DessiaObject.__init__(self, name='generator')

def generate(self, min_mass: float, max_gold: int = None,
max_iter: int = None):
solutions = []
count = 0
for i in range(1, len(self.items)+1):
for combination in combinations(self.items, i):
solution = KnapsackPackage(
items=combination,
allowed_mass=self.knapsack.allowed_mass,
name=f'Package {i}')

if min_mass <= solution.mass <= self.knapsack.allowed_mass:
if max_gold is not None:
if solution.golds <= max_gold:
solutions.append(solution)
count += 1
else:
solutions.append(solution)
count += 1

if max_iter is not None and count == max_iter:
return solutions

return solutions``````

To make the `Generator` more flexible and make trade-offs simpler, we can add parameters like:

• `min_mass` to delete solutions that don’t respect the minimal mass
• `max_gold` to ensure that the solutions created don’t exceed a given number of gold items
• `max_iter` to limit the number of solutions created so that the generation don’t take too much time