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. static int minOblozenia(int[] punkty, int k) {
  2.   int maksimum = max(punkty);
  3.   for (int i = 1; i <= maksimum; i++) {
  4.     int ilePrzejsc = 0;
  5.     for (int p = 0; p < punkty.Length; 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. static void Main(string[] args) {
  2.   Console.WriteLine("Ile produktów jest w każdym punkcie:");
  3.   string[] dane = Console.ReadLine().Split(' ');
  4.   int[] punkty = new int[dane.Length];
  5.   for(int i = 0; i < dane.Length; i++) {
  6.     punkty[i] = Convert.ToInt32(dane[i]);
  7.   }
  8.   Console.Write("Podaj maksymalną ilość kursów\n k = ");
  9.   int k = Convert.ToInt32(Console.ReadLine());
  10.   int wynik = minOblozenia(punkty, k);
  11.   if (wynik == 0) {
  12.     Console.WriteLine("Brak rozwiązania");
  13.   } else {
  14.     Console.WriteLine("Potrzebna pojemność: {0}", wynik);
  15.   }
  16.   Console.ReadKey();
  17. }