Na ile sposobów można wydać 100 zł? :)

Mając do dyspozycji nominały od 100 zł do 1 zł, trzeba znaleźć ich wszystkie możliwe kombinacje tzn.

  1. 100 zł
  2. 50 zł + 50 zł
  3. 50 zł + 20 zł + 20 zł + 10 zł
  4. 50 zł + 20 zł + 10 zł + 10 zł + 10 zł itd... ostatni to same złotówki.

Zadanie wydaje się być trywialne... stworzyłem prostą strukturę i odejmowałem pierw złotówki dodając do tablicy dynamicznej wynik... ale jakoś mi nie idzie, proszę ekspertów o rade :P

4 lata, 6 miesięcy temu | edytowane przez: Manveru 422441527

  • EDIT: Rozwiązanie optymalne (tj. najszybsze) i najbardziej eleganckie oparte jest o programowanie dynamiczne. Wcześniejszy pomysł o drzewo, jak również rozwiązanie kolegi michu niestety jest nieoptymalny i obciążający pamięciowo.

    Kod w C wygląda następująco:

     #include <stdio.h>
     #define CEL 100
     #define NOMINALY 7
     int main() {
       int i, j;
    
       // tablica z wartościami
       int t[CEL + 1];
       for (i = 0; i <= CEL; i++) { t[i] = 0; }
       t[0] = 1;
    
       // tablica z nominałami
       int n[] = {1, 2, 5, 10, 20, 50, 100};
    
       // zaczynamy zabawę
       for (i = 0; i < NOMINALY; i++) {
         for (j = n[i]; j <= CEL; j++) {
           t[j] = t[j] + t[j - n[i]];
         }     
       }
    
      printf("%d\n", t[CEL]);
    }
    

    Gwoli wytłumaczenia algorytmu:

    Wszystko odbywa się w jednej tablicy, jak widać z kodu. O wiele łatwiej jednak rozpisać to sobie na kartce w tablicy. Liczba kolumn w takiej tabeli równa jest liczbie celu, tj. 100. W wierszach tabeli znajdują się kolejne (rosnące) nominały.

    W komórkach tabeli znajdą się informacje, na ile sposobów można uzyskać daną kwotę, korzystając z danego i poprzednich nominałów, tj. w komórce (CEL=45, NOMINAŁ=5) znajduje się informacja na ile sposobów możemy osiągnąć sumę 45zł korzystając z nominałów 5, 2 i 1. Widać z tego, że odpowiedź znajdziemy w komórce (CEL=100, NOMINAŁ=10). Kwestią pozostaje wypełnienie tabeli;)

    Dorzucamy sobie jeszcze (nie widać tego w kodzie) wirtualne kolumną ("0"), wypełnioną jedynkami, i wirtualny wiersz (też "0") wypełniony zerami.

    Tabelę wypełniamy jednak bardzo prosto: dodajemy wiersz wyżej, kolumną o bieżący nominał niższą., czyli komórka (CEL=45, NOMINAŁ=5) będzie równa (CEL=45, nominał = 2) + (CEL=45-5=40, NOMINAŁ=5).

    Polecam rozpisanie sobie na kartce i poczytanie o programowaniu dynamicznym.

    A, byłbym zapomniał. Wynik to 4563:D


    A ja bym to zrobił przez przeszukiwanie w głąb.

    Czyli w ten sposób:

    1. Zacznij od pustej tablicy
    2. Na początek tablicy wrzuć pierwszy nominał
    3. Jeżeli suma elementów w tablicy jest mniejsza od 100, dorzuć element mniejszy/równy od ostatniego taki, żeby suma była nie mniejsza niż 100.
    4. Jeżeli suma elementów jest równa 100, odrzuć ostatni element, na koniec tablicy dorzuć następny element mniejszy od odrzuconego i przejdź do punktu 3.

    Trochę jestem już zmulony, ściągnąłem szkła kontaktowa a jeszcze nie mam okularów, więc naprawdę nie mam siły tego implementować:)

    Jak będziecie grzeczni, zaimplementuję jutro po południu.

  • Najprościej chyba przez rekurencję. Zaczynasz od 0, w pętli jedziesz po nominałach które nie powodują przekroczenia sumy i dla każdego z tych nominałów wywołujesz rekurencyjnie przekazując jako parametr bieżącą sumę i listę dotychczasowych nominałów. Po osiągnięciu sumy 100 zł wypisujesz listę.

    Głębokość rekurencji nie przekroczy 100, więc nie ma problemu ze stosem. Jedyne co może być problematyczne, to że wyniki będą się powtarzać, różniąc tylko kolejnością nominałów. Możesz ten problem zniwelować zaczynając pętlę wewnątrz procedury rekurencyjnej od ostatniego nominału użytego na poprzednim poziomie rekurencji - wtedy ciągi będą zawsze malejące.

    EDIT: Rozwiązanie w C# wygląda jakoś tak:

    class Kasjer
    {
        private readonly int[] _nominaly = new int[] {1, 2, 5, 10, 20, 50, 100};
    
        public void Wydaj(int suma)
        {
            Wydaj(suma, 0, new int[suma], -1);
        }
    
        private void Wydaj(int suma, int wydane, int[] ostatnie, int liczba)
        {
            foreach(int nominal in _nominaly)
            {
                if (liczba != -1 && nominal < ostatnie[liczba])
                    continue;
    
                if(wydane + nominal > suma)
                    break;
    
                if(wydane + nominal == suma)
                {
                    for(int i=0; i<=liczba; i++)
                    {
                        Console.Write(ostatnie[i] + ",");
                    }
                    Console.Write(nominal);
                    Console.WriteLine();
                    Console.WriteLine();
                    break;
                }
    
                ostatnie[liczba+1] = nominal;
                Wydaj(suma, wydane + nominal, ostatnie, liczba+1);                    
            }
        }
    }
    

    Wywołanie rzecz jasna przez

    Kasjer k = new Kasjer();
    k.Wydaj(100);
    

  • To zagadnienie nazywa się integer partition. Zwykle potrzebną informację jest to na ile sposobów można rozłożyć daną liczbę (służy do tego funkcja p(n) z artykułu). Udało mi się jednak znaleźć przykład algorytmu w Matlabie, który robi to, o co chodzi. Warto też zajrzeć tu (lista implementacji z różnych książek) i tu (w Pythonie, niestety bez możliwości określenia nominałów).

    Niemniej jednak za każdym razem jest to rekurencja i rozwiązania są podobne zwykle do tego, co zaprezentował michu.

  • trochę zoptymalizuj :-)
    Spróbuj może tak:
    Pierwsza możliwość 100: ją możesz rozłożyć na 50 i 50, dwie takie same wartości więc, bierzesz pierwszą 50tkę i rozkładasz ją na kolejne możliwośći 20 20 10 i masz teraz:
    * 100
    * 50 50
    * 20 20 10 , 50
    Drugą 50 tkę nie sądze żebyś musiał rozkładać dalej. Dalej masz 20ścia i rozkładasz je na 10 i 10, dochodzi teraz możliwość rozłożenia 20 10 10 10 50, kolejną 10tkę rozkładasz podobnie, mam nadzieje że rozumiesz o co mi chodzi :-)

    Edit: Piotreks dobrze zauważył że - zresztą, komentarz ;-)

    W takim razie, lecimy tak jak Michu pisał, rekurencyjnie jeszcze.
    100: rozkładamy na:
    50 50
    20 20 20 20 20
    10 10 10 10 10 10 10 10 10 10
    itd.
    Czyli na wielokrotność kolejnych nominałów
    50 możemy rozłożyć jak pisałem na: 20 20 10, 10 10 10 10 10, itd. Ogólnie z każdego przypadku z pierwszego rozłożenia, bierzemy tylko pierwszą liczbę i ją dalej rozkładamy:
    100
    - 50 50
    -- 20 20 10 50
    --- 10 10 * 20 10 50
    ---- 5 5 * 10 20 10 50

    ---- 2 2 2 2 2 * 10 20 10 50
    ---- 1
    10 * 10 20 10 50
    -- 10 10 10 10 10 *50



    - 20 20 20 20 20


    Albo wiecie co, Michu dobrze pisze, to ja tu próbuje osiągnąć nie wiadomo co :D


    EDit, kolejny:
    Może by jeszcze wykorzystać dosyć jasny fakt że każdy nominał zawsze tak samo można rozłożyć? i to sobie zwyczajnie zapisać w tablicy i potem zamiast go jeszcze raz rozkładać, pobrać dane z tej tablicy :-)

  • nilphilus Doskonale rozumiem, bo robię to samo ;) i nie widzę w Twoim sposobie optymalizacji :P Tą drugą pięćdziesiątkę też muszę rozłożyć. Samo wykonanie nie jest trudne ale optymalizacja... kwestia dobrego pomysłu którego ja nie mam.

  • Witam, jak się dzisiaj czujesz? Mam nadzieję, że wszystko jest dobrze. Nazywam się na stałym poziomie. W poszukiwaniu człowieka, który rozumie znaczenie miłości, zaufania i wiary w siebie, a nie ten, kto widzi miłość jako jedyny sposób zabawy, ale dojrzały człowiek z Nicei wizję tego, co na świecie jest wszystko o, a po przeczytaniu profilu tutaj (matchperfect) I wziął interes w ciebie, więc zarzuty odpowiedź mi w tym e-mail (constantduke10@hotmail.com. Będę bardzo szczęśliwy, aby przeczytać odpowiedzi tak, że ja wysłać moje zdjęcie dla Ciebie możemy wówczas zacząć wiedzieć więcej o sobie nawzajem. Dziękuję za przeczytanie mojego maila i być Bless.

    stałej (constantduke10@hotmail.com))

    Hello, how are you doing today? i hope all is well. My name is constant., In search of a man who understand the meaning of love as Trust and faith in each other rather than one who sees love as the only way of fun, but a matured Man with Nice Vision of what the world is all about, and after reading your profile here in(matchperfect ) I took Interest in you, so pleas reply me with this Email (constantduke10@hotmail.com. i will be very happy to read your reply so that i will send my picture to you then we can start know more about each other. Thanks for reading my mail and be Bless.

    constant (constantduke10@hotmail.com))

Zaloguj się, aby dodać swoją odpowiedź