# knapsack problem - Select items to get maximum profit without exceeding the bag's capacity.
import random

weights = [2, 3, 4, 5, 9]
values = [3, 4, 5, 8, 10]
capacity = 10

size = 30
generations = 100
mutation = 0.1

def fitness(x):
    w = sum(x[i]*weights[i] for i in range(5))
    v = sum(x[i]*values[i] for i in range(5))
    return v if w <= capacity else 0

def create():
    return [[random.randint(0,1) for _ in range(5)]
            for _ in range(size)]

def select(pop):
    return max(random.sample(pop,3), key=fitness)

def crossover(a,b):
    p = random.randint(1,4)
    return a[:p]+b[p:]

def mutate(x):
    for i in range(5):
        if random.random() < mutation:
            x[i] = 1-x[i]
    return x

pop = create()

for gen in range(generations):
    pop.sort(key=fitness, reverse=True)
    best = pop[0]

    new = [best]
    while len(new) < size:
        child = crossover(select(pop),select(pop))
        new.append(mutate(child))

    pop = new

best = max(pop, key=fitness)
print("Selected Items:", best)
print("Total Weight:", sum(best[i]*weights[i] for i in range(5)))
print("Maximum Profit:", fitness(best))
