7 miesięcy temu
autor: halish

4

• Bezpośrednie łącze
• Komentarze (6)
• Oznacz jako niewłaściwe

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.

7 miesięcy temu
autor: michu

9

• Bezpośrednie łącze
• Komentarze (6)
• Oznacz jako niewłaściwe

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);

7 miesięcy temu
autor: newton

2

• Bezpośrednie łącze
• Dodaj komentarz
• Oznacz jako niewłaściwe

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.

7 miesięcy temu
autor: nilphilus

1

• Bezpośrednie łącze
• Komentarze (5)
• Oznacz jako niewłaściwe

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
---- 110 * 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 :-)

7 miesięcy temu
autor: micpyc

0

• Bezpośrednie łącze
• Komentarze (2)
• Oznacz jako niewłaściwe

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.