# Rucksackproblem

gegenstaende = [(3.5, 375), (2.5, 300), (2.0, 100), (3.0, 225), (1.0, 50),
                (1.75, 125), (0.75, 75), (3.0, 275), (2.5, 150), (2.25, 50)]
grenzgewichtRucksack = 15.0

# Funktionen zur Erzeugung einer Lösung

anzahlIndividuen = 50
mutationswahrscheinlichkeit = 0.05

from random import *

def erzeugeIndividuum():
    individuum = []
    for j in range(len(gegenstaende)):
        gen = randint(0, 1)
        individuum = individuum + [gen]
    return individuum

def erzeugePopulation():
    population = []
    for i in range(anzahlIndividuen):
        individuum = erzeugeIndividuum()
        population = population + [individuum]
    return population
        
def fitness(individuum):
    gewicht = 0
    wert = 0
    for j in range(len(gegenstaende)):
        if individuum[j] == 1:
            gewicht = gewicht + gegenstaende[j][0]
            wert = wert + gegenstaende[j][1]
    if gewicht > grenzgewichtRucksack:
        wert = 0
    return wert

def kreuzung(individuum1, individuum2):
    stelle = randint(0, len(gegenstaende)-1)
    neuesIndividuum1 = individuum1[:stelle+1] + individuum2[stelle+1:]
    neuesIndividuum2 = individuum2[:stelle+1] + individuum1[stelle+1:]
    return (neuesIndividuum1, neuesIndividuum2)

def mutation(individuum):
    stelle = randint(0, len(gegenstaende)-1)
    if individuum[stelle] == 0:
        individuum[stelle] = 1
    else:
        individuum[stelle] = 0
    return individuum

def selektionElternteil(population):
    p = randint(0, anzahlIndividuen-1)
    q = randint(0, anzahlIndividuen-1)
    elternKandidat1 = population[p]
    elternKandidat2 = population[q]
    if fitness(elternKandidat1) > fitness(elternKandidat2):
        elternteil = elternKandidat1
    else:
        elternteil = elternKandidat2
    return elternteil

def naechstePopulation(population):
    neuePopulation = []
    while len(neuePopulation) < anzahlIndividuen:
        eltern1 = selektionElternteil(population)
        eltern2 = selektionElternteil(population)
        (kind1, kind2) = kreuzung(eltern1, eltern2)
        w1 = random()
        if w1 <= mutationswahrscheinlichkeit:
            kind1 = mutation(kind1)
        w2 = random()
        if w2 <= mutationswahrscheinlichkeit:
            kind2 = mutation(kind2)
        neuePopulation = neuePopulation + [kind1, kind2]
    return neuePopulation

def maxFitness(population):
    maxIndividuum = population[0]
    maximumFitness = fitness(population[0])
    for individuum in population[1:]:
        if fitness(individuum) > maximumFitness:
            maxIndividuum = individuum
            maximumFitness = fitness(individuum)
    return (maxIndividuum, maximumFitness)

def loesungGenetischerAlgorithmus():
    population = erzeugePopulation()
    zaehler = 0
    while zaehler < 20:
        population = naechstePopulation(population)
        zaehler = zaehler + 1
    loesung = maxFitness(population)
    return loesung
    
# Test
for i in range(20):
    print(loesungGenetischerAlgorithmus())