Algorytm zachłanny

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ć?

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
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.

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.

1

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)

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