W jaki sposób „Problem kompletacji pizzy” rozwiązuje się za pomocą technik programowania dynamicznego?

9

Problem zbierania pizzy przez Winklera:

  • Okrągłe ciasto do pizzy z nplasterkami, w którym plasterek ima powierzchnię, S_itj. Powierzchnia jest inna dla każdego kawałka ciasta.
  • Zjadacze Alice i Bob na zmianę wybierają plastry, ale niegrzeczne jest tworzenie wielu luk w cieście (uważaj to za niedozwolone).
    • Zatem każdy zjadacz jest ograniczony do wzięcia jednego z dwóch plasterków sąsiadujących z otwartym obszarem. Alice jest pierwsza i obaj jedzą tyle ciastek, ile to możliwe.

W jaki sposób algorytm programowania dynamicznego określiłby, ile ciasta zjada Alice, jeśli zarówno Alice, jak i Bob grają idealnie, aby zmaksymalizować zużycie pizzy?

Moje zrozumienie:

W ogólnym problemie DP idziemy dalej do znajdowania podproblemów, które można wizualizować za pomocą drzewa rekurencji lub, ściślej, za pomocą DAG. Tutaj nie znajduję żadnej wskazówki, by znaleźć tutaj pod-problemy.

Tutaj, dla danego zestawu S_i, musimy zmaksymalizować obszar plasterków zjadanych przez Alice. Będzie to zależeć od wyboru permutacji plasterków pizzy spośród permutacji (n-1). Wybranie wycinka o maksymalnej powierzchni spośród dwóch opcji dostępnych w każdych n \ 2 ruchach, jakie otrzyma Alice, da nam całkowitą powierzchnię odcięcia dla permutacji. Musimy znaleźć obszar plasterka dla wszystkich takich permutacji. A potem maksimum z nich.

Czy ktoś może mi pomóc, jak iść naprzód?

algorithms dynamic-programming Amit Shekhar
źródło

Odpowiedzi:

5

Zacznij od rozważenia plasterków właśnie umieszczonych w rzędzie i możesz wybrać jeden z dwóch końców. W tym przypadku, zakładając, że twoja kolej na wybranie jest jasne, że tak pizzaAmount(slices)jest

  1. Jeśli nie ma pizzy, wynik wynosi 0
  2. Jeśli jest tylko jeden wynik, to ten kawałek
  3. Jeśli są co najmniej dwa plasterki, wynik jest następujący:

(przy użyciu składni Python)

max(slices[0] + sum(slices[1:]) - pizzaAmount(slices[1:]),
    slices[-1] + sum(slices[:-1]) - pizzaAmount(slices[:-1]))

innymi słowy, powinieneś rozważyć obie alternatywy i że po zabraniu plastra dostaniesz całą pozostałą pizzę, z wyjątkiem wyniku połączenia rekurencyjnego (ponieważ twój przyjaciel zastosuje tę samą strategię).

Możesz to zaimplementować za pomocą DP (lub zapamiętywania), ponieważ tablica jest rzeczywiście ustalona i możesz po prostu rozważyć jako parametry pierwszy i ostatni indeks plasterka.

Aby rozwiązać pierwotny pełny problem, wystarczy wypróbować wszystkie plasterki jako plaster początkowy i wybrać ten, który maksymalizuje wynik.

6502
źródło
Dzięki „6502”. Mogę lepiej zwizualizować problem, korzystając z podpowiedzi „biorąc pod uwagę plasterki właśnie umieszczone w rzędzie i wybierając jeden z dwóch końców”. Biorąc pod uwagę relację powtarzalności, dba również o optymalny wybór przeciwnika. Wkrótce opublikuję formalny algorytm. Dzięki chłopaki!!
Ciekawe, jaka jest kolejność złożoności tego algorytmu? 0 (n * 2 ^ n)?
@Akron: Tak właśnie byłoby bez dynamicznego programowania lub zapamiętywania. Możesz jednak skorzystać z faktu, że wynik pizzaAmountnie zależy tylko od tego, jaki jest indeks początkowy i końcowy pozostałych plasterków, a nie od kolejności, w której plasterki pizzy zjadłeś już Ty i Twój przyjaciel, więc możesz zapisać wynik w macierz, aby uniknąć ponownego obliczenia. Kolejność algorytmu wynosi zatem O (n ** 2).
6502
Jeśli ktoś nadal stara się zrozumieć, ten link ma bardzo ładne wytłumaczenie.
Amit Shekhar
3

Dla części pizzy określ F(i,j)jako maksymalną liczbę osób, które może zjeść pierwszy plasterek. Plastry części pizzy (i,j)to:

if i <= j than slices i, i+1, ..., j-1, j
if i > j than slices i, i+1, ..., n-1, n, 1, 2, ..., j-1, j
and we don't define it for whole pizza, abs(i-j) < n-1

Zdefiniuj R(i,j)(ile pozostało drugiej osobie) jako sum(S_x, x in slices(i,j)) - F(i,j).

Z:

F(i,i) = S_i,
F(i,j) = max( S_i + R(i+1,j), S_j + R(i,j-1) ),

maksymalna, jaką Alicja może zjeść, obliczana jest przez:

max( S_i + F(i+1, (i-1) if i > 1 else n) ).
Ante
źródło