Algorytm zachłanny

Odpowiedz Nowy wątek
2018-11-05 21:15
0

Dzieci na podwórku ulepiły n kul śnieżnych (1<=n<=100000) o różnych masach. Postanowiły
wszystkie te kule skleić w jedną wielką kulę, a zadanie to powierzyły Jasiowi. Będzie on kolejno
wybierał parę kul i je zlepiał w jedną. Ten krok będzie powtarzał aż zostanie mu tylko jedna kula.
Wysiłek włożony w każde zlepienie dwóch kul jest równy sumie ich mas. Jaś ma głowę nie od
parady i nie chce się zbytnio namęczyć, więc próbuje znaleźć taką kolejność lepienia, by jego
sumaryczny wysiłek był jak najmniejszy.

Przykładowo dla 3 kul o masach 5, 1, 3 najmniejszy możliwy wysiłek to 13 – najpierw zlepiamy
kule nr 2 i 3 (1+3=4) i nowo powstałą kulę o masie 4 dolepiamy do kuli nr 1 (4+5=9), czyli w
sumie wysiłek Jasia wynosi 13 (9+4).

Pomoże ktoś? Jak algorytm ma wybierać za każdym razem które kule złączyć? Jakim kryterium ma się kierować?

Gdzie Szukałeś i nie Znalazłeś odpowiedzi, Masz jakiś kod? - lion137 2018-11-05 21:19
nie mam kodu. mam zadanie i muszę napisać do niego kod - spamgolden 2018-11-05 21:24
@spamgolden: mógłbyś zatytułować wątek w sposób opisujący problem? - somekind 2018-11-06 11:41

Pozostało 580 znaków

2018-11-05 21:42
3

Może po prostu:

  1. wagi kul wrzucasz do kopca
  2. dopóki jest więcej niż 1 element :
    2.1 wyciągasz 2 elementy min z kopca
    2.2 obliczasz sumę
    2.3 sumę dodajesz do kosztu
    2.4 sumę dodajesz do kopca
dlaczego elementy minimalne? - spamgolden 2018-11-05 21:44
Bo chciałeś zachłannie? :-) - yarel 2018-11-05 21:48
tylko czy jeśli będziemy brać zawsze kule o najmniejszej wadze, to czy algorytm będzie optymalny, czyli wysiłek będzie najmniejszy? - spamgolden 2018-11-05 21:50
Intuicyjnie wydaje się optymalny, bo minimalizujemy w każdym kroku pracę do wykonania. Może wystarczy wziąć 3 kule i rozważyć przypadki a=b=c, a=b<c, a<b=c, a<b<c i założyć, że gdyby istniał algorytm optymalny, który nie wymaga wyboru minimum na początku, to dawałby koszt taki a taki. Później kontr przykład i utrącenie każdego wariantu i sprzeczność z założeniem, które bierze minimum na początku. A później uogólnienie przez indukcję? Nie wiem, tak sobie głośno myślę ;-) - yarel 2018-11-06 09:10
Wydaje mi się, że @yarel ma rację. Jakich kul byś nie wziął, to zawsze musisz policzyć ich łączną sumę + sumy cząstkowe. Łączna suma jest zawsze taka sama, to co możesz zminimalizować, to właśnie sumy cząstkowe. A to zrobisz, sumując aktualnie najlżejsze kule (należy pamiętać o aktualizacji kopca po każdym zsumowaniu dwóch kul). - Pyxis 2018-11-06 11:51

Pozostało 580 znaków

2018-11-06 10:41
1

i nie chce się zbytnio namęczyć, więc próbuje znaleźć taką kolejność lepienia, by jego
sumaryczny wysiłek był jak najmniejszy.

Może coś źle zrozumiałem, ale wychodzi mi że sumaryczny wysiłek zawsze będzie ten sam niezależnie od kolejności zlepiania kul.
Jeśli nie ma żadnych innych warunków to to jest po prostu dodawanie kolejnych mas kul i kolejność nie ma znaczenia.

edytowany 1x, ostatnio: wm23, 2018-11-06 10:43
Weź taki zdegenerowany przykład [0,0,0,0,0,0,1] i zawsze bierzesz 1. Koszt1=1, Koszt2=1+1, Koszt3=1+1+1 itd. - yarel 2018-11-06 10:52
weź sobie prosty przykład 1 2 3, zlepiamy 1 i 2 przy wysiłku 3, mamy 3 3 zlepiamy je przy wysiłku 6, co daje nam w sumie 9; a teraz na odwrót zlepiamy 2 3 przy wysiłku 5, mamy 5 1 które zlepiamy przy wysiłku 6 co daje nam w sumie 11; więc kolejność jak najbardziej ma znaczenie. - neves 2018-11-06 10:54
OK, dobra, czyli miałem rację ... źle zrozumiełem ;) "Przeoczyłem" że masa zlepionej kuli zostanie użyta ponownie - wm23 2018-11-06 11:13

Pozostało 580 znaków

2018-11-06 16:40
0

A mógłby ktoś do tego pseudokod napisać? Taki prosty. Byłbym bardzo wdzięczny. Zaczynam dopiero algorytmike i chciałbym mieć jakiś wzór. Z góry wielkie dzięki za pomoc.

Pozostało 580 znaków

2018-11-06 17:05

Wg algorytmu yarela:

minheap = SomeLibrary.minheap()
cost = 0

for ball in input:
  minheap.push(ball)

while minheap.length() > 1:
  a = minheap.pop()
  b = minheap.pop() # masz gwarantowane przez warunek pętli, że będą co najmniej dwa obiekty
  cost += a + b
  minheap.push(a + b)
edytowany 1x, ostatnio: Althorion, 2018-11-06 17:20

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0