Genetic Algorithm

import random

def calculate_fitness(bits, items, threshold):
    total_cost = 0
    total_weight = 0

    #print("Items in fitness check:", items)

    for i, bit in enumerate(bits):
        if bit == 1:
            item = items[i]
            total_cost += item[1][0]
            total_weight += item[1][1]

    if total_weight <= threshold:
        return total_cost

    return 0

def perform_selection(items):
    backpack = []

    for _ in range(len(items)):
        if random.random() > 0.5:
            backpack.append(1)
        else:
            backpack.append(0)

    return backpack

def crossover_split(parent_a, parent_b):
    """ Single point crossover split """
    split_index = 3

    parent_1, splice_1 = parent_a[:split_index], parent_a[split_index:]
    parent_2, splice_2 = parent_b[:split_index], parent_b[split_index:]
    parent_1.extend(splice_2)
    parent_2.extend(splice_1)

    return parent_1, parent_2

def mutate(bits):
    """ Mutate by flipping bits pseudo-randomly """
    output = ''
    threshold = 0.9

    for bit in bits:
        if random.random() > threshold:
            if bit == 1:
                output += '0'
            else:
                output += '1'
        else:
            output += str(bit)

    #print("I:", ''.join([str(bit) for bit in bits]))
    #print("O:", output)
    return [int(bit) for bit in output]

def generate_population(items, n):
    selections = []

    for _ in range(n):
        selections.append(perform_selection(items))

    return selections

generations = 5
population_size = 10

items = {
    0: ("laptop", (500, 2200)),
    1: ("headphones", (150, 160)),
    2: ("coffee mug", (60, 350)),
    3: ("notepad", (40, 333)),
    4: ("water bottle", (30, 192))
}

# The initial population is entirely random
population = generate_population(items, 10)

# Apply the algorithm
for generation in range(generations):
    print(f"Generation {generation + 1}.")

    # calculate the fitness score for each of the members of the population
    fitness_scores = []

    for entry in population:
        fitness_scores.append((entry, calculate_fitness(entry, items, 3000)))

    best = sorted(fitness_scores, key=lambda xy: xy[1])[::-1]

    elitism_count = 2
    elite = best[0:elitism_count]
    next_population = []

    for entry in elite:
        bits, score = entry
        next_population.append(bits)

    while len(next_population) < population_size:
        index_a = random.randint(0, len(items))
        index_b = random.randint(0, len(items))

        while index_b == index_a:
            index_b = random.randint(0, len(items))

        results = crossover_split(
            population[index_a], population[index_b])

        next_population.extend(results)

    print("Next population:", next_population)
    mutated_population = []

    for entry in next_population:
        mutation = mutate(entry)
        mutated_population.append(mutation)

    population = mutated_population

print("Finished.")