Czerpaki

WItam, mam zadanie o treści.

Posiadamy dwa czerpaki o pojemnościach M i N litrów. Pusty pojemnik o nieskończonej pojemności. Podaj sposób napełnienia pojemnika K litrami wody. Wodę można wlewać i wylewać tylko pełnymi czerpakami. Podaj ilość ruchów dla każdego czerpaka. Jeśli danym czerpakiem wlewamy traktujemy to z plusem do sumy ruchów a jeśli wylewamy to z minusem.

Wiem, że nie zawsze jest to wykonywalne i mam wtedy wyświetlić stosowny komunikat.

Nie chce odpowiedzi wprost chciałbym was prosić o jakieś wskazówki

Dzięki!!

1. Wyznacz liczby litrów które jesteś w stanie dodać stosując te twoje dwa czerpaki M i N. Oczywiste wartości to M, N, ale też np. abs(M-x*N) jeśli nalejesz do większego a potem odlejesz z niego x-razy używając mniejszego czerpaka.
2. Rozłóż K na sumę złożoną z powyższych wartości.

Policzyłbym to programowaniem dynamicznym, dla każdej wartości k rozważasz 4 ruchy +m,-m,+n,-n, zaczynasz od k = 0, i wypełniasz tabele o rozmiarze na oko do k + NWW(n,m), złożoność pseudowielomianowa.

Albo tak jak w problemie z wydawaniem reszty, tyle że z ujemnymi nominałami, też powinna śmigać.

Gdy M i N są względnie pierwsze (gcd(M, n) = 1), wtedy ich najmniejszą kombinacją liniowa jest 1, z czego wynika, że można odmierzyć dowolnek.

Tak by wyglądało rozwiązanie programowaniem dynamicznym, nie było podanego języka, więc najłatwiej zrobić w kompilowalnym pseudokodzie:). Brak rozwiązania jest gdy k nie jest wielokrotnościągcd(M, N).:

def extends(x, k, M, N):
	"""returns a dictionary object"""
	return {M + x: 'add M', x + N: 'add N',
			x - M: 'sub M', x - N: 'sub N'}


def pouring_water(M, N, k, st=0):
	if k % math.gcd(M, N) != 0: return [None]
	if k == st:
		return [st]
	done = set() # set of explored
	nxt = [[st]] # list of lists of ways 
	while nxt:
		p = nxt.pop(0)
		x = p[-1] # last element in p
		d = extends(x, k, M, N)
		for (s, a) in d.items(): # iterate over map items
			if s not in done:
				done.add(s)
				new_p = p + [a, s]
				if k == s:
					return new_p
				else:
					nxt.append(new_p)

def main():
	print(pouring_water(5, 3, 4)) # -> [0, 'add M', 5, 'add M', 10, 'sub N', 7, 'sub N', 4]
	# Die Heard :-D:-D

if __name__ == "__main__":
    main()

EDYCJA: Dodałem zbiór wykonanych akcji, done (żeby nie powtarzać), bez tego rozwiązanie jest złe, działa, ale nie efektywnie.