Strona główna » Algorytmy » Artykuły » McNuggetowy problem
 

McNuggetowy problem

https://mattomatti.com/a92

Wstęp

W wielu restauracjach część produktów jest sprzedawana w konkretnej ilości. Przykładowo w McDonald's® Chicken McNuggetsTM są sprzedawane w pudełkach po 4, 6, 9 i 20. Oznacza to, że często nie jest możliwe zamówienie tylu kurczaków ile byśmy chcieli. McNuggetowy problem ma za zadanie podpowiedzieć czy istnieje szansa uzyskać żądaną liczbę n wybranego produktu.

Przykład

Załóżmy, że do restauracji przychodzi grupka 7 osób. Chcieliby kupić tyle Chicken McNuggetsTM, aby można je było równo rozdzielić. W tym celu należy sprawdzać każdą wielokrotność 7. Niestety 7 jest niemożliwe do uzyskania, ponieważ kupując pudełko z 6 nie ma możliwości dokupienia jednej sztuki. Można by spróbować kupić pudełko z czterema, ale wtedy też nie można uzyskać pozostałych 3. W tym przypadku odpowiedzią jest 21, ponieważ można kupić 2 pudełka po 6 i jedno po 9 co daje w sumie 21. Wtedy każdy zje po 3 sztuki.

Implementacja

Założenia

Każda możliwa liczba sztuk do uzyskania to kombinacja liniowa liczb 4, 6, 9 oraz 20. Ze względu na fakt, że 20 jest wielokrotnością 4 to kombinacja liniowa upraszcza się do 4, 6, 9. Do rozwiązania zadania można użyć algorytmu chciwego. Należy jednak pamiętać, że bardzo często istnieje więcej niż poprawna konfiguracja kurczaków, aby uzyskać daną liczbę.

Czy kupię?

Na początek warto napisać funkcję czyKupie(), która odpowie na zasadnicze pytanie: czy dana liczba n jest kombinacją liniową liczb 4, 6 oraz 9. W tym celu wystarczy począwszy od największej liczby zmniejszać wartość n, a na koniec sprawdzić czy w pudełkach jest dokładnie taka ilość jak chcieliśmy:

  1. bool czyKupie(int n) {
  2.   zdejmij(n, 9);
  3.   zdejmij(n, 6);
  4.   zdejmij(n, 4);
  5.   return (n == 0);
  6. }

Funkcja korzysta z funkcji zdejmij(), która odejmuje od wartości n wartość a dopóki jest taka możliwość. Pozwala to na uniknięcie powtarzania trzy razy pętli while.

  1. void zdejmij(int &n, int a) {
  2.   while (n >= a)
  3.     n -= a;
  4. }

Rozkład

Założenia

W celu znalezienie wszystkich konfiguracji dla danej liczby n warto wykorzystać rekurencję, aby sprawdziła wszystkie konfiguracje i wypisała je o ile znaleziona konfiguracja w sumie daje liczbę n. Wszystkie poprzednie liczby będą przechowywane w utworzonej wcześniej liście. Nietrudno się domyślić, że dana liczba n może mieć maksymalnie cztery razy mniej niż wynosi n składników co wynika z faktu, ze najmniejsze pudełko zawiera 4 sztuki.

Tego typu zadanie jest nieco trudniejsze i warto rozbić je na prostsze funkcje. Dane będą wypisywane bezpośrednio na konsole przez co nie istnieje potrzeba zapamiętywania znalezionych rozkładów. Pisanie kodu najlepiej zacząć od funkcji czyKupieRozklad(). Funkcja ta alokuje pamięć gdzie zapisane zostaną kolejne liczby rozkładu:

  1. void czyKupieRozklad(int n) {
  2.   int* l = new int[n / 4];
  3.   sprobujKupic(l, n);
  4.   delete l;
  5. }

(2.) Alokacja listy w zależności od liczby n. (3.) Wywołanie funkcji sprobujKupic(), która sprawdza kolejne konfiguracje pudełek. (4.) Dealokacja używanej pamięci.

Dobieranie pudełek

Dobieraniem kolejnych pudełek zajmuje się funkcja sprobujKupic(), która w każdym wywołaniu sprawdza ile ma sztuk i dobiera kolejne. Funkcja znajduje wszystkie prawidłowe konfiguracje. Podczas szukania istnieje założenie, że w następnym wywołaniu dobierane jest pudełko zawierające nie więcej sztuk niż dołożono poprzednio:

  1. void sprobujKupic(int* l, int n, int a = 9, int index = 0) {
  2.   if (n >= 4) {
  3.     if (n >= 9 && a >= 9) {
  4.       dokup(l, n, 9, index);
  5.       sprobujKupic(l, n, 9, index);
  6.       zwroc(n, 9, index);
  7.     }
  8.     if (n >= 6 && a >= 6) {
  9.       dokup(l, n, 6, index);
  10.       sprobujKupic(l, n, 6, index);
  11.       zwroc(n, 6, index);
  12.     }
  13.     if (n >= 4 && a >= 4) {
  14.       dokup(l, n, 4, index);
  15.       sprobujKupic(l, n, 4, index);
  16.       zwroc(n, 4, index);
  17.     }

(2.) Sprawdź czy można dołożyć jakiekolwiek pudełko. Jeśli tak to (3. - 17.) sprawdź dla każdego rodzaju pudełka czy można je dołożyć oraz czy dokładane pudełko jest nie większe niż poprzednio dołożone. Po wybraniu pudełka (4.) dokup pudełko, (5.) szukaj następnego pudełka (albo wypisz rozkład), ale przed próbą dołożenia kolejnego pudełka (6.) zwróć "zakupiony" produkt.

  1.   } else {
  2.     if (n == 0) {
  3.       for (int i = 0; i + 1 < index; i++)
  4.         cout << l[i] << ", ";
  5.       cout << l[index - 1] << endl;
  6.     }
  7.   }
  8. }

(18.) Jeśli nie można dołożyć już żadnego pudełka to: (19.) sprawdź czy zakupiono n sztuk we wszystkich pudełkach. Jeśli tak to (20. - 22.) wypisz znaleziony rozkład.

Kupowanie i zwracanie pudełek

W trakcie wybierania kolejnych pudełek dochodzi do ich zakupu poprzez funkcję dokup(). Funkcja ta polega na (2.) dopisaniu jakie pudełko został zakupione oraz (3.) zmniejsza ile zostało sztuk do kupienia.

  1. void dokup(int* l, int& n, int a, int& index) {
  2.   l[index++] = a;
  3.   n -= a;
  4. }

Po sprawdzeniu wszystkich możliwości z daną konfigurację istnieje potrzeba zwrócenia zakupionego towaru, dlatego została napisana funkcja zwroc(), która (2.) usuwa ostatni element na liście zakupionych pudełek oraz (3.) zwiększa ilość sztuk do zakupienia:

  1. void zwroc(int &n, int a, int& index) {
  2.   index--;
  3.   n += a;
  4. }

Testowanie funkcji

Poniższa funkcja main() wczytuje od użytkownika ile sztuk chciałby zakupić, a poniżej wypisane zostają wszystkie możliwe konfiguracje, aby taki wynik uzyskać:

  1. int main () {
  2.   int n;
  3.   cout << "Ile sztuk? ";
  4.   cin >> n;
  5.   cout << "Mozliwe konfiguracje:\n";
  6.   czyKupieRozklad(n);
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Napisz program, który wczyta od użytkownika liczbę k, a następnie listę liczb o k elementach. Następnie program powinien spytać o liczbę n - ile sztuk chciałby zakupić użytkownik. Program powinien na ekran wypisać wszystkie możliwe konfiguracje dla podanej liczby używając tylko pudełek wczytanych początkowo na liście.

Przykładowo dla danych:

  1. 5
  2. 2 3 5 8 12
  3. 13

Program wypisze na ekran:

  1. 8, 5
  2. 8, 3, 2
  3. 5, 5, 3
  4. 5, 3, 3, 2
  5. 5, 2, 2, 2, 2
  6. 3, 3, 3, 2, 2
  7. 3, 2, 2, 2, 2, 2