Problem kuriera i wagi paczek (nie komiwojażer!)

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Shelim
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 20 maja 2009, o 16:40
Płeć: Mężczyzna
Podziękował: 1 raz

Problem kuriera i wagi paczek (nie komiwojażer!)

Post autor: Shelim »

Witam serdecznie!

Szczerze mówiąc nie wiem za bardzo do jakiego działu to zawrzeć, bo to algorytmika, ale może ktoś mnie naprowadzi; Formalnie nie wiem nawet jak ten problem się nazywa, więc z Wikipedii nie mogę skorzystać;

Opowiastka:
Mamy n paczek o różnych masach wyrażonych liczbami naturalnymi dodatnimi. Musimy je rozdzielić między m kurierów, przy czym dane m \(\displaystyle{ \le}\) n. Znaleźć algorytm rozdziału paczek tak, żeby różnica między najmniej a najbardziej obciążonym kurierem była jak najmniejsza. Paczek nie wolno dzielić na mniejsze części.

Zadanie wydawałoby się banalne, gdyby nie jeden szkopuł - nie ma założenia równomiernego rozkładu mas paczek.

Jak ja to próbowałem ugryźć:
Wejście: liczby \(\displaystyle{ n, m}\); paczki \(\displaystyle{ A_{1}, A_{2}, ..., A_{n}}\)
Wyjście: zbiory paczek \(\displaystyle{ B_{1}, B_{2}, ..., B_{m}}\)
Opis działania:
1. Szeregujemy paczki w kolejności nierosnącej według masy, tworząc ciąg \(\displaystyle{ C_{1}, C_{2}, ..., C_{n}}\)
2. Dla każdego i od 1 do m, do zbioru \(\displaystyle{ B_{i}}\) dodajemy paczkę \(\displaystyle{ C_{i}}\)
3. Przypisujemy zmiennej k wartość m
4. Dodajemy 1 do k
5. Jeżeli k > n, zakończ algorytm
6. Obliczamy wartość każdego zbioru (tzn. sumę mas paczek)
7. Do zbioru o najmniejszej wartości dodajemy paczkę \(\displaystyle{ C_{k}}\)
8. Wracamy do punktu 4.

Nie potrafię jednak tego udowodnić (wymyślone na podstawie obserwacji ciekawych przypadków)
xpenguin
Użytkownik
Użytkownik
Posty: 79
Rejestracja: 19 kwie 2009, o 19:09
Płeć: Kobieta
Lokalizacja: Radom
Pomógł: 6 razy

Problem kuriera i wagi paczek (nie komiwojażer!)

Post autor: xpenguin »

Mi to trochę pachnie zasadą szufladkową Dirichleta ( ... Dirichleta)... nawet bardzo Myślę, że można z tego skorzystać do formalnego dowodu, zresztą porównaj przykłady na Wikipedii.

Zakładając, że każdy kurier musi mieć jakąś paczkę, to ponieważ \(\displaystyle{ m \le n}\), to co najmniej jeden z nich dostanie przynajmniej jedną paczkę. "Nadprogramowych" paczek będzie oczywiście \(\displaystyle{ n-m}\). Tak jak w Twoim algorytmie, ustawiamy paczuszki od najlżejszej do najcięższej, i gdy już każdy kurier będzie miał po jednej, "wracamy" do tego z najlżejszą i znowu rozdajemy, zaczynając od najlżejszej z "nadprogramowych" paczek, i tak do momentu, aż paczki się skończą... Logiczne jest, że w ten sposób różnica między najbardziej obładowanym a najmniej obładowanym będzie najmniejsza.
Shelim
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 20 maja 2009, o 16:40
Płeć: Mężczyzna
Podziękował: 1 raz

Problem kuriera i wagi paczek (nie komiwojażer!)

Post autor: Shelim »

Kontrprzykład, który podał pan doktor:

Weźmy n=5, m=2,
A1=100,
A2=80,
A3=70,
A4=60,
A5=50.

Po moim algorytmie:
B1=100+60 = 160
B2=80+70+50 = 200

Poprawny wynik:
B1=100+80 = 180
B2=70+60+50 = 180

Ktoś ma jeszcze jakieś sugestie?
ODPOWIEDZ