Nuggets

Code-Stücke können hier veröffentlicht werden.
Antworten
mysterion
User
Beiträge: 8
Registriert: Dienstag 3. Januar 2017, 17:38

Hallo Zusammen!

Ich versuche gerade eine Funktion zu schreiben, die zu einer Zahl N alle Möglichkeiten anzeigt, N Nuggets zu kaufen. Die Nuggets können jeweils in 6er-, 9er- und 20er-Packungen gekauft werden. Mein Skript sieht bisher so aus:

Code: Alles auswählen

import numpy

def nuggets(N):
	a = N / 6
	b = N / 9
	c = N / 20
	if N < 6:						
		print("Zu wenig Nuggets.")
	elif N % 6 == 0:
		if N % 9 == 0:
			if N % 20 == 0:
				print(a, '6er-Packungen oder', b, '9er-Packungen oder', c,'20er-Packungen.')
			else:
				print(a, '6er-Packungen oder', b, '9er-Packungen.')
		elif N % 20 == 0:
			print(a, '6er-Packungen oder', c, '20er-Packungen.')
		else:
			print(a, '6er-Packungen.')
	elif N % 9 == 0:
		if N % 20 == 0:
			print(b, '9er-Packungen oder', c, '20er-Packungen.')
		else:
			print(b, '9er-Packungen.')
	elif N % 20 == 0:
		print(c, '20er-Packungen')
	else:
Mir fehlen jetzt noch die Möglichkeiten, wie man die Packungen kombinieren kann. Hat jemand eine Idee wie ich das hinbekomme?

LG Mysterion
Zuletzt geändert von Anonymous am Mittwoch 8. Februar 2017, 14:37, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
sebastian0202
User
Beiträge: 168
Registriert: Montag 9. Mai 2016, 09:14
Wohnort: Berlin

Meinst du ungefähr so?

Code: Alles auswählen


def nuggets(nuggets):
    packungen = [20, 9, 6]
    korb = {}
    for packung in packungen:
        if nuggets >= packung:
            korb[packung] = int(nuggets / packung)
            nuggets = nuggets % packung
    korb['rest'] = nuggets
    return korb


if __name__ == '__main__':
    print(nuggets(107))
    # {'rest': 1, 20: 5, 6: 1}

Sirius3
User
Beiträge: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

@sebastian0202: es gibt Ganzzahldivision nuggets // packung oder gleich divmod:

Code: Alles auswählen

def nuggets(nuggets, packungen=[20, 9, 6]):
    korb = {}
    for groesse in packungen:
        anzahl, nuggets = divmod(nuggets, groesse)
        if anzahl:
            korb[groesse] = anzahl
    korb['rest'] = nuggets
    return korb
mysterion
User
Beiträge: 8
Registriert: Dienstag 3. Januar 2017, 17:38

Erstmal danke für die schnellen antworten! Ich hab da aber doch noch eine Frage:

Könnte man das ganze auch mit einer while-Schleife oder rekursiv lösen? Die Aufgabe ist für die Uni und das ist gerade unser Thema. :D
Sirius3
User
Beiträge: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

@mysterion: jede for-Schleife kann man auch rekursiv oder als while-Schleife formulieren. Ob das mit vertretbarem Aufwand geht, hängt vom Problem ab. Hier ist die for-Schleife jedenfalls am besten.
BlackJack

Wobei die vorliegenden Funktionen nicht das Problem lösen *alle* Möglichkeiten N Nuggets zu kaufen zu ermitteln. *Das* klingt auch eher nach einem sinnvollen Einsatz für Rekursion als da jetzt eine einfache, iterative Schleife zu ersetzen.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Bin kein Experte für Kombinatorik. Mein Ansatz wäre jedenfalls, eine erste Lösung mit möglichst vielen Packungen (also bevorzugt 6er) zu finden und dann weitere Lösungen zu suchen, bei denen die Anzahl der Packungen schrittweise abnimmt. Das Maximum an Packungen wäre ceil(nuggets / 6.0), das Minimum ceil(nuggets / 20.0), sofern ich nichts übersehen habe. Und hierzu würde ich dann eine find_combination(num_packages) schreiben.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Hier mal auf Basis von product() aus dem itertools-Modul:

Code: Alles auswählen

from __future__ import division, print_function
from itertools import product
from math import ceil

def get_combinations(n, sizes):
    min_packages = ceil(n / max(sizes))
    max_packages = ceil(n / min(sizes))
    for num_packages in range(min_packages, max_packages + 1):
        combinations = product(sizes, repeat=num_packages)
        for combination in combinations:
            if sum(combination) == n:
                yield combination

def make_unique(sequences):
    unique = set(tuple(sorted(seq)) for seq in sequences)
    for sequence in unique:
        yield sequence

def print_combinations(n, sizes):
    combinations = make_unique(get_combinations(n, sizes))
    for combination in combinations:
        print(
            ', '.join(map(str, combination))
        )

def main():
    sizes = [6, 9, 20]
    for i in range(75):
        print(i, 'Nuggets:')
        print_combinations(i, sizes)
        print('\n')

if __name__ == '__main__':
    main()
Wird allerdings ab 70 Nuggets zunehmend langsamer. Sicherlich kriegt man das mit NumPy effizienter hin, aber auf dem Gebiet bin ich leider nicht so bewandert.
Sirius3
User
Beiträge: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

@snafu: ich habe Deinen Algorithmus nicht ganz nachvollzogen, aber der Trick ist, um viele unnötige Kombinationen zu vermeiden, das beim Produkt die kleinste Größe wegzulassen und diese direkt zu berechnen:

Code: Alles auswählen

from itertools import product
def iter_bundle_combinations(nuggets, bundle_sizes=[20, 9, 6]):
    combinations = [range(nuggets // size + 1) for size in bundle_sizes[:-1]]
    for amounts in product(*combinations):
        remaining = nuggets - sum(a*b for a,b in zip(bundle_sizes, amounts))
        if remaining >= 0:
            amount, remaining = divmod(remaining, bundle_sizes[-1])
            if not remaining:
                yield amounts + (amount,)

def main():
    for nuggets in range(75):
        print(nuggets, 'Nuggets:')
        print(list(iter_bundle_combinations(nuggets)))
        print()
 
if __name__ == '__main__':
    main()
Antworten