Build your first Bot

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.

Additional parameters

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

Add displays to your bot

Displays can be personalized and implemented for each class created in Python. To learn more about displays, check out the chapter called Quick Start with Dessia SDK.

You can find the displays we have created for this bot on our GitHub page (opens in a new tab).

Upload your bot to the platform

Once you have created your Python file and stored it in a Git package, you can read the chapter called Upload a bot to the platform.

If you have trouble creating a Git package, consider using our automated package creator called dessia_bot_template (opens in a new tab). We will soon be releasing an app that you can download on your computer to make your life easier on this matter. If you want more information about this app, please contact us.

🔨 Create your first AI App Install required packages