Ctrl+K

Tutorials#

In this example, a regular decision tree with next_unique_node is implemented to find the bast solution for a Knapsack Problem. A selection of items among a collection of 10 items, having a mass and a value, have to be made to yield the highest value while fitting in a knapsack of maximum 30kg. To solve this problem the regular decision tree will be composed of 10 levels (a selection of maximum 10 items) and each node will have 10 possibilities, one for each item. However an item can’t be picked twice so this example uses next_unique_node.

from dectree import RegularDecisionTree


# Creating a class for the items
class Item:
    def __init__(self, mass, value, name):
        self.mass, self.value, self.name = mass, value, name

    def __repr__(self):
        return f'{self.name} : value = {self.value} ; mass = {self.mass}'


# Knapsack maximum weight
max_mass = 30

# List of all the items
items = [Item(4, 10, 'item1'),
         Item(5, 11, 'item2'),
         Item(6, 14, 'item3'),
         Item(7, 18, 'item4'),
         Item(8, 20, 'item5'),
         Item(9, 24, 'item6'),
         Item(10, 27, 'item7'),
         Item(11, 28, 'item8'),
         Item(12, 30, 'item9'),
         Item(13, 33, 'item10')]

# Creating a regular decision tree
tree = RegularDecisionTree(np=[len(items)] * len(items))

result = None
max_value = 0
while not tree.finished:
    # Stocking information about current node
    current_mass = sum(items[i].mass for i in tree.current_node)
    current_value = sum(items[i].value for i in tree.current_node)
    current_items = [items[i] for i in tree.current_node]

    # Checking viability of current node
    valid = False if current_mass > max_mass else True

    if valid and current_value > max_value:
        result = current_items
        max_value = current_value

    # Going to next node
    tree.next_unique_node(current_node_viability=valid)

However, knowing that order of the items inside a solution doesn’t matter, the algorithm can be improved using next_sorted_unique_node instead of next_unique_node. It is then equivalent to a regular decision tree with 10 levels, on for each item, and only 2 possibilities for each node : take the corresponding item or not.

# Creating a regular decision tree
tree = RegularDecisionTree(np=[2] * len(items))

result = None
max_value = 0
while not tree.finished:
    # Stocking information about current node
    current_mass = sum(items[item_i].mass * i for item_i, i in enumerate(tree.current_node))
    current_value = sum(items[item_i].value * i for item_i, i in enumerate(tree.current_node))
    current_items = [items[item_i] for item_i, i in enumerate(tree.current_node) if i]

    # Checking viability of current node
    valid = False if current_mass > max_mass else True

    if valid and current_value > max_value:
        result = current_items
        max_value = current_value

    # Going to next node
    tree.next_node(current_node_viability=valid)
Show Source