Strona główna » Algorytmy » Artykuły » Dystrybucja Prezentów
 

Dystrybucja Prezentów

https://mattomatti.com/a0185

Wstęp

Optymalizacja dystrybucji pozwala zminimalizować koszty transportu, ale też oszacować czy dany model jest możliwy do zrealizowania. W tym artykule zostanie przedstawiony do rozwiązania jeden z takich problemów.

Sklep zamawia produkty na prezenty u wielu dostawców. Dostawcy znajdują się w różnych miejscach miasta, więc nie jest możliwe zabranie produktów od kilku dostawców równocześnie. Przyjmujemy, że paczki są równej wielkości. Chcemy, aby wszystkie produkty zostały przewiezione w maksymalnie w k kursach. Przy każdym kursie chcemy, aby ilość przewożonych produktów była jak najmniejsza, ponieważ będzie można do tego zadania wykorzystać mniejszy i zarazem tańszy w eksploatacji pojazd.

Zadanie polega na napisaniu programu, który stwierdzi ile paczek trzeba przewieźć podczas każdego kursu, aby wykonać ich maksymalnie k i odebrać wszystkie produkty od dostawców.

Przykład

Mamy 4 sklepy z których trzeba przewieźć następujące ilości produktów 1, 2, 2, 4 w maksymalnie k = 6.

Najprostsze rozwiązanie i najbardziej oszczędne pod względem kursów jest przewiezienie podczas każdego kursu 4 produkty. Wtedy wystarczą 4 kursy, ale potrzebny będzie dość duży pojazd, a w tym zadaniu stać nas na k kursów i chcemy zaoszczędzić na samochodzie jaki wypożyczamy czyli innymi słowy chcemy przy każdym kursie przewieźć jak najmniej paczek. (Warto zauważyć, że maksimum tablicy to największa i w miarę rozsądna opcja - każda większa wartość tylko obniży efektywność przewozu).

Zmniejszmy ilość paczek do zaledwie dwóch. Potrzeba wtedy łącznie wykonać 5 kursów, ale potrzebujemy samochodu dwa razy mniej pojemnego. Warto zauważyć, że tym razem pojazd nie jedzie pełny tylko w przypadku pierwszego sklepu, ale pozostałe cztery kursy wykonuje wykorzystany w pełni. W poprzednim przykładzie część kursów wykonywał na wpół pusty.

Dalsze zmniejszanie pojemności samochodu jest możliwe - można przewieźć podczas każdego kursu tylko jedną paczkę, ale jak łatwo policzyć potrzeba wtedy, aż 9 kursów, więc nie będzie to rozwiązanie, które mieści się w przyjętych na początku założeniach tj. maksymalna ilość kursów została podana na 6.

Podsumowując najlepszym rozwiązaniem jest wynająć pojazd, który pomieści 2 produkty. Wykona on wtedy 5 kursów.

Implementacja

Funkcja minOblozenia() wymaga podania dwóćh argumentów: tablicy produkty w której na pozycji i jest zapisane ile produktów oczekuje w i-tym sklepie oraz k - maksymalna ilość kursów, która może zostać wykonana. Funkcja zwraca ile produktów musi podczas jednego kursu przewieźć pojazd, albo 0, gdy jest to niemożliwe.

  1. int minOblozenia(int * punkty, int n, int k) {
  2.   int maksimum = max(punkty, n);
  3.   for (int i = 1; i <= maksimum; i++) {
  4.     int ilePrzejsc = 0;
  5.     for (int p = 0; p < n; p++) {
  6.       ilePrzejsc += punkty[p] / i;
  7.       if (punkty[p] % i != 0) {
  8.         ilePrzejsc++;
  9.       }
  10.     }
  11.     if (ilePrzejsc <= k) {
  12.       return i;
  13.     }
  14.   }
  15.   return 0;
  16. }

Na początek wyznaczamy maksimum, a następnie sprawdzamy ile kursów wykonamy dla każdej pojemności pojazdu. Podczas wyliczania kursu należy pamiętać, że ilość produktów podzieloną przez pojemność samochodu musi zostać zaokrąglona w górę. Jeśli po obliczeniach potrzebnych kursów jest mniej niż określone k to należy zwrócić wynik. Jeśli jednak żadne rozwiązanie nie mieści się w założeniach to należy zwrócić 0.

Testowanie funkcji

W celu przetestowania funkcji można uruchomić poniższy kod, który wczyta potrzebne dane, a następnie zinterepretuje wynik.

  1. int main () {
  2.   int n, k;
  3.   cout << "Ile punktow z produktami?\n n = ";
  4.   cin >> n;
  5.   int * produkty = new int[n];
  6.   cout << "Podaj ile produktow jest w kazdym punkcie:\n";
  7.   for (int i = 0; i < n; i++)
  8.     cin >> produkty[i];
  9.   cout << "Podaj maksymalna ilosc kursow\n k = ";
  10.   cin >> k;
  11.   int wynik = minOblozenia(produkty, n, k);
  12.   if (wynik == 0) {
  13.     cout << "Brak rozwiazania";
  14.   } else {
  15.     cout << "Potrzebna pojemnosc: " << wynik;
  16.   }
  17.   system("pause");
  18.   return 0;
  19. }