Strona główna Polish Python Coders Group
   Strona główna   Pomoc Zaloguj się Rejestracja  
Witamy, Gość. Zaloguj się lub zarejestruj.
Czy dotarł do Ciebie email aktywacyjny?

Zaloguj się podając nazwę użytkownika, hasło i długość sesji

Aktualności: PyStok #42 - wystąpią Łukasz Langa i Dominik Kozaczko
Szukaj Szukaj
Strony: [1]   Do dołu
Drukuj
Wątek: Mam Monety o Nominale A=[1,2,5,10...] w ilości B =[1,0,1,12...] zapłacić S  (Przeczytany 128 razy)
« : 18:53 18/05/19 »
krzychupython Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 7


Możecie pomóc w tym zadaniu. Męczę się z tym od kilku dni. Mianowicie chodzi o to że np. Mamy monety o nominale A = [1, 2, 5, 10, 20, 100, 200] w ilości B=[1 ,1 ,3, 10, 10, 2, 5]
i musimy zapłacić S=18 zł. Wtedy Odp jest "TAK"  [1,1,2,0,0,0,0] 1*1+1*2+2*5+0*10+0*20+0*100+0*200 
Zapisane
« Odpowiedz #1 : 20:22 18/05/19 »
DJangoL Offline
Professional Python User

Zobacz profil
***

Reputacja: 30
Wiadomości: 427


W czym problem? Szukasz ogólnego rozwiązania (dla dowolnych list o dowolnej wielkości)?
Zapisane
« Odpowiedz #2 : 20:32 18/05/19 »
krzychupython Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 7


Tak
Zapisane
« Odpowiedz #3 : 21:01 18/05/19 »
DJangoL Offline
Professional Python User

Zobacz profil
***

Reputacja: 30
Wiadomości: 427


Dla list o 7 elementach, jak w zadaniu, wyszły mi dwa rozwiązania (dla Sumy S = 18):

Kod
(1, 1, 1, 1, 0, 0, 0)
(1, 1, 3, 0, 0, 0, 0)

Jak chcesz listy o dowolnym rozmiarze, to ja bym tutaj zastosował rekurencję.
Niewykluczone, ze specjaliści od modułu itertools wymyślą lepsze rozwiązanie Uśmiech

Tu kod dla tupli / listy 7-elementowej.

Kod
A = (1, 2, 5, 10, 20, 100, 200)
B = (1, 1, 3, 10, 10, 2, 5)
 
SZUKANA = 18
 
for a in range(B[0] + 1):
   for b in range(B[1] + 1):
       for c in range(B[2] + 1):
           for d in range(B[3] + 1):
               for e in range(B[4] + 1):
                   for f in range(B[5] + 1):
                       for g in range(B[6] + 1):
                           tuplaB = (a, b, c, d, e, f, g)
                           tuplaS = (A[i]*tuplaB[i] for i in range(len(A)))
                           suma = sum(tuplaS)
                           if suma == SZUKANA:
                               print(tuplaB)
                               print(suma)
Zapisane
« Odpowiedz #4 : 11:58 19/05/19 »
krzychupython Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 7


Dzięki bardzo Uśmiech
Zapisane
« Odpowiedz #5 : 10:44 21/05/19 »
Guaz Offline
Expert Python User

Zobacz profil
****

Reputacja: 69
Płeć: Mężczyzna
Wiadomości: 513


Ja osobiście bym to zrobił całkiem inaczej, przekształciłbym to na słownik (wartość: ilość) [lub listę dwuwymiarową], a następnie szedł od największej wartości, jeśli jest mniejsza niż kasa potrzebna do wypłaty, to stosował ten banknot/monetę o ile się da. To najprostszy algorytm wypłat, największa możliwa suma.

Ale bez przekształceń, to najprościej będzie tak:
Kod
value = [1, 2, 5, 10, 20, 100, 200]
quantity = [1 ,2 ,3, 10, 10, 2, 5]
used = []
index = -1 #~ Pointing at 200 value
 
requested = 49
rest = requested
while index >= -len(value):
   if value[index] <= rest and quantity[index] > 0:
       rest -= value[index]
       quantity[index] -= 1
       used.append(value[index])
       if rest == 0:
           break
   else:
       index -= 1
 
if rest == 0:
   print("Wydałem:", used, "czyli:", sum(used), "co powinno być równe:", requested)
else:
   print("Nie mogłem wydać reszty, próbowałem wydać:", used, "czyli:", sum(used),"a wymagano:", requested)
 
Bez urazy DjangoL, ale ta masa pętli, to zdecydowana przesada, można się w tym pogubić Uśmiech.
A co do specjalistów od itertools, najpewniej chodziło ci o `itertools.product`, który iteruje kolejne możliwe kolejności o danej długości, ale nie ma chyba takiej funkcji która pozwala zdefiniować ile maksymalnie razy może wystąpić dany element na podstawie drugiej listy ;d

Oczywiście da się to zrobić jeszcze optymalniej, ale to taki najprostszy do napisania sposób jaki widzę Uśmiech
Zapisane

Python 3.5+ / Mint

Daje wędkę zamiast ryby. Chyba że ktoś się chce czegoś nauczyć, wtedy chętnie pomogę każdemu.
Za rybę niestety trzeba zapłacić Z politowaniem.
Strony: [1]   Do góry
Drukuj
Skocz do:  

© 2007 - 2019 Polish Python Coders Group
Powered by SMF 1.1.21 | SMF © 2006-2009, Simple Machines | Theme by PixelSlot