Peter’s Peppers

Bei HP Codewars war 2012 als Aufgabe 5 eine Lösung für folgendes Problem zu entwickeln:

Ein Geschäft verkauft Paprika in Paketen zu 6, 11 oder 13 Paprikas. Der Preis pro Verpackung ist gleich, nur die Größen sind verschieden. Ein Skript soll nun eine Zahl n (n < 1000) erhalten und die kleinste Kombination von Paketen für den Versand finden. 13er-Pakete sollen bevorzugt werden.

Als Beispiele werden Bestellungen von 42, 55, 27 und 88 Paprikas gegeben. Das Skript soll seine Ausgabe in einer bestimmten Form erledigen:

42 peppers can be packed most economically in:
1 package of 13
1 package of 11
3 packages of 6
5 total packages.

bzw.

27 peppers cannot be packed.

Das Problem sieht stark nach einem Graphentheorie-Problem aus, was ich aber noch nicht beherrsche. Folgendes Skript arbeitet korrekt, ist aber bei einem größeren n nicht mehr sehr performant:

def packen(n):
    ''' Algorithmus, der die beste Kombination
    von 13er-, 11er- und 6er-Paketen Paprika ermitteln
    und zurueckgeben soll. Kann keine Loesung gefunden
    werden, dann wird 0,0,0 zurueckgegeben

    '''
    ergebnisliste = []
    
    for a in range(0,n // 13 + 1):
        for b in range(0,n // 11 + 1):
            for c in range(0,n // 6 + 1):
                if a * 13 + b * 11 + c * 6 == n:
                    # print(a,b,c)
                    ergebnis = a,b,c
                    ergebnisliste.append(ergebnis)

    ergebnisliste.sort()     
    if len(ergebnisliste) == 0:
        return 0,0,0
    else:
        return ergebnisliste.pop()


bestellungen = [6,31,42,55,27,88,79,802,999,964]

for bestellung in bestellungen:
    a,b,c = packen(bestellung)

    packages_gesamtzahl = a + b + c

    if a == 0 and b == 0 and c == 0:
        print("{} peppers cannot be packed.\n".format(bestellung))
    else:
        print("{} peppers can be packed most economically in:".format(bestellung))

        for package, value in zip([a,b,c], [13,11,6]):
            if package > 1:
                print("{} packages of {}".format(package,value))
            elif package == 1:
                print("{} package of {}".format(package,value))
                
        print("{} total packages.\n".format(packages_gesamtzahl))

Ich denke, dass das Problem besser zu lösen sein müsste. In einem ersten Schritt ist mir jedenfalls für die Funktion eine Vereinfachung eingefallen:

def packen(n):
    ''' Algorithmus, der die beste Kombination
    von 13er-, 11er- und 6er-Paketen Paprika ermitteln
    und zurueckgeben soll. Kann keine Loesung gefunden
    werden, dann wird 0,0,0 zurueckgegeben
 
    '''    
    for a in range(n // 13,-1,-1):
        for b in range(0,n // 11 + 1):
            for c in range(0,n // 6 + 1):
                if a * 13 + b * 11 + c * 6 == n:
                    # print(a,b,c)
                    ergebnis = a,b,c
                    return ergebnis
    return 0,0,0

Ich kann die Funktion eindampfen, weil ich nicht mehr alle möglichen Kombinationen erfassen will, sondern jetzt vom größtmöglichen Faktor von 13 starte und gegen 0 runterzähle. Der erste "Treffer" kann direkt zurückgegeben werden, weil hier die Bedingung - größtmögliche Anzahl der 13er-Pakete - erfüllt ist. Für die Anzahl der 11er- und 6er-Pakete gibt es in der Aufgabenstellung keine Bedingung.