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.

C++C#
Python
  1. def minOblozenia(punkty, k):
  2.   maksimum = max(punkty)
  3.   for i in range(1, maksimum + 1):
  4.     ilePrzejsc = 0
  5.     for punkt in punkty:
  6.       ilePrzejsc += punkt // i
  7.       if punkt % i != 0:
  8.         ilePrzejsc += 1
  9.     if ilePrzejsc <= k:
  10.       return i
  11.   return 0

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.

C++C#
Python
  1. print("Ile produktów jest w każdym punkcie:")
  2. punkty = [int(x) for x in input().split()]
  3. k = int(input("Podaj maksymalną ilość kursów\n k = "))
  4. wynik = minOblozenia(punkty, k)
  5. if (wynik == 0):
  6.   print("Brak rozwiązania")
  7. else:
  8.   print("Potrzebna pojemność:", wynik)