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 itemmass: a positive integer representing the weight of the itemprice: a positive integer representing the value of the item
- Knapsack
name: a string representing the name of the knapsackallowed_mass: a positive integer representing the maximum weight that the knapsack can hold
- KnapsackPackage
name: a string representing the name of the knapsack packageitems: a list ofItemcontained in the knapsack packageallowed_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):
passThe 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 Listclass 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 colorclass 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 += 1The 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,
name: str = 'generator'):
self.items = items
self.knapsack = knapsack
DessiaObject.__init__(self, name=name)
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}')
count += 1
if min_mass <= solution.mass <= self.knapsack.allowed_mass:
if max_gold is not None:
if solution.golds <= max_gold:
solutions.append(solution)
else:
solutions.append(solution)
if max_iter is not None and count == max_iter:
return sorted(solutions, key=lambda x: x.price,
reverse=True)
return sorted(solutions, key=lambda x: x.price, reverse=True)To make the Generator more flexible and make trade-offs simpler, we can add parameters like:
min_massto delete solutions that don’t respect the minimal massmax_goldto ensure that the solutions created don’t exceed a given number of gold itemsmax_iterto 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).
Here is what they look like:
- For the
Itemclass, here are its 2D and 3D displays
def volmdlr_primitives(self, z_offset: float = 0.):
height_vector = self.mass * Z3D / 2
frame = Frame3D(origin=O3D + height_vector / 2 + z_offset * Z3D,
u=X3D,
v=Y3D,
w=height_vector,
name='frame ' + self.name)
primitives = [Block(frame=frame,
color=self.rgb,
name='block ' + self.name)]
return primitives
@plot_data_view("2D display for Item")
def display_2d(self, y_offset: float = 0.):
contour = ClosedPolygon2D([
Point2D(-0.5, -0.5 + y_offset),
Point2D(0.5, -0.5 + y_offset),
Point2D(0.5, 0.5 + y_offset),
Point2D(-0.5, 0.5 + y_offset)])
surface_style = SurfaceStyle(
color_fill=f'rgb({self.rgb[0]*255},{self.rgb[1]*255},{self.rgb[2]*255}')
primitive1 = contour.plot_data(surface_style=surface_style)
text_style = TextStyle(text_color='rgb(0, 0, 0)',
font_size=None,
text_align_x='center',
text_align_y='middle')
primitive2 = Text(comment=f'{self.mass} kg',
position_x=0,
position_y=0.4 + y_offset,
text_style=text_style,
text_scaling=True,
max_width=0.5,
multi_lines=False)
primitive3 = Text(comment=f'{self.price} €',
position_x=0,
position_y=-0.1 + y_offset,
text_style=text_style,
text_scaling=True,
max_width=0.5,
multi_lines=False)
return PrimitiveGroup(primitives=[primitive1, primitive2, primitive3])- For the
Knapsackclass, here is its 3D displays
def volmdlr_primitives(self):
height_vector = (self.allowed_mass + 0.5) * Z3D / 2
frame = Frame3D(origin=O3D + height_vector / 2,
u=1.1 * X3D,
v=1.1 * Y3D,
w=height_vector + 0.1 * Z3D,
name='frame ' + self.name)
primitives = [Block(frame=frame,
alpha=0.3,
name='block ' + self.name)]
return primitives- For the
KnapsackPackageclass, here are its 2D and 3D displays
def volmdlr_primitives(self):
primitives = super().volmdlr_primitives()
z_offset = 0
for item in self.items:
item_primitives = item.volmdlr_primitives(z_offset=z_offset)
primitives.extend(item_primitives)
z_offset += item.mass / 2 + 0.05
return primitives
@plot_data_view("2D display for KnapsackPackage")
def display_2d(self):
primitives = []
y_offset = 0
for item in self.items:
primitive_groups = item.display_2d(y_offset=y_offset)
primitives.extend(primitive_groups.primitives)
y_offset += 1.1
text_style = TextStyle(text_color='rgb(0, 0, 0)',
font_size=None,
text_align_x='center',
text_align_y='middle')
primitive1 = Text(comment=f'{self.mass} kg',
position_x=0,
position_y=-1.5,
text_style=text_style,
text_scaling=True,
max_width=1,
multi_lines=False)
primitive2 = Text(comment=f'{self.price} €',
position_x=0,
position_y=-2,
text_style=text_style,
text_scaling=True,
max_width=1,
multi_lines=False)
primitives.extend([primitive1, primitive2])
return PrimitiveGroup(primitives=primitives)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.