Pytanie Tworzenie maksymalnej konfiguracji za pomocą programowania dynamicznego


Mam pewne trudności, próbując rozwiązać ten problem, który umieszczam poniżej. Mam kilka pomysłów, które próbowałem. Najpierw jednak wybrałem wszystkie kombinacje krotek N i zamówiłem je, ale implementacja była brzydka i miała zwolnić. Myślę, że istnieje podejście do programowania dynamicznego w tym problemie. Mam problem z utworzeniem konfiguracji. Po tym, myślę, że wiem, jak rozwiązać problem.

Stwierdzenie problemu:

Biorąc pod uwagę wysokość H (1 <= H <= 1 000 000 000), musimy znaleźć sekwencję wysokości od N krotek, która jest większa lub równa H. Istnieje kilka warunków: Każda z N krotek ma wagę, wysokość i siłę. Siła krotki wskazuje maksymalną ilość całkowitej masy, która może znajdować się na górze tej krotki.

Pytanie prosi o znalezienie maksymalnej wartości bezpieczeństwa stosu. Wartość bezpieczeństwa to masa, którą można dodać, nie przekraczając żadnej z niższej siły krotki. Jeśli nie jest to możliwe, wydrukuj -1.

WKŁAD:

Pierwszy wiersz wejścia zawiera N i H.

Następne N wierszy wejściowych każdy opisuje krotkę, podając jej wysokość, waga i siła. Wszystkie są dodatnimi liczbami całkowitymi co najwyżej 1 miliard.

PRÓBNE WEJŚCIE:

4 10

9 4 1

3 3 5

5 5 10

4 4 5

PRZYKŁADOWE WYJŚCIE:

2


11
2017-12-14 22:24


pochodzenie


Wyjaśnij problem lepiej. Jaka jest rola Hgrać? O czym mówisz? Możesz spróbować wyjaśnić te rzeczy dla wprowadzenia próbki i pokazać, w jaki sposób dane wyjściowe są właściwą odpowiedzią. - Pradhan
Masz rację, że istnieje dynamiczne rozwiązanie programistyczne. Zaczyna się od sortowania krotek od najsilniejszego do najsłabszego. Teraz, gdy budujesz stosy, zawsze umieszczasz bieżącą krotkę na stosie. Nigdy nie musisz utrzymywać stosów, które mają co najmniej tak wysoką wysokość i punkt krytyczny co najmniej tak niski. - btilly
Każda krotka może być użyta tylko raz, prawda? - MikeMB
Jaka jest wielkość wielkości krotek? - MikeMB
Kiedy powiesz biorąc pod uwagę wysokość H, jest H maksymalna wysokość listy krotek? - Rerito


Odpowiedzi:


Cóż, skoro nikt nie opublikował rozwiązania, zrobię to.

Biorąc pod uwagę dwie krotki, t1 = (h1, w1, s1) i t2 = (h2, w2, s2)możemy je również połączyć
[t1 over t2] lub [t2 over t1]. W każdym przypadku możemy traktować wynik jako kolejną krotkę; na przykład,

t3 = [t1 over t2] = (h1 + h2, w1 + w2, min(s1, s2 - w1))

(Wynikająca z tego siła krotki nie może być wyższa niż jedna z dwóch mocy krotek komponentów, a siła krotki dolnej jest zmniejszona o wagę krotki na wierzchu, wynikowa siła może być ujemna).

Bez względu na kolejność kompozycji, wynikowa wysokość i waga krotki są takie same; jednak wynikowa siła może różnić się w zależności od zamówienia. Interesują nas krotki o maksymalnej sile, więc bierzemy maksimum z dwóch możliwych wartości. Biorąc pod uwagę powyższe, określmy skład jako

t1 + t2 = (h1 + h2, w1 + w2, max(min(s1, s2 - w1), min(s2, s1 - w2)))

Wynikowe krotki mogą z kolei być skomponowane z innymi krotkami i tak dalej.

To, czego potrzebujemy, to znalezienie maksymalnej siły spośród wszystkich wynikowych krotek wysokości H, ponieważ maksymalna wartość bezpieczeństwa Żądana w pytaniu jest faktycznie siłą wynikowej krotki.

Tak więc możemy ustawić maksymalną moc początkową na -1, zacznij komponować krotki i, gdy tylko znajdziemy jakąś wysokość H lub więcej, zaktualizuj bieżącą maksymalną siłę, jeśli siła krotki jest większa.

Zasada nr 1: Wynikowa siła krotki nie może być wyższa niż jedna z dwóch mocy krotek komponentów, więc podczas komponowania krotek, ilekroć znajdziemy siłę mniejszą lub równą bieżącej wartości maksymalnej, możemy ją odrzucić, ponieważ żadna krotka, w której jest będzie składnikiem może mieć siłę wyższą niż aktualny maks.

Zasada 1a: Możemy nawet odrzucić krotkę, która została użyta do zaktualizowania aktualnej maksymalnej siły, ponieważ pytanie nie pyta nas o samą krotkę, tylko maksymalną wartość, a ta krotka nie wygeneruje żadnych lepszych maksimów w żadnej innej kombinacji.

Zasada 2: A teraz przyjrzyjmy się odgórnie. Każdy stos n = 2k krotki mogą być postrzegane jako złożone z dwóch krotek, z których każda składa się ze stosu k krotki; dla n = 2k + 1, dwa stosy mają rozmiar k i k + 1.

Więc budujemy, aby:

  1. lista początkowych krotek;
  2. lista krotek wynikających ze stosów dwóch;
  3. listę krotek wynikających ze stosów trzech, z krotkami utworzonymi przez wzięcie jednej krotki z listy [1] i jednej krotki z listy [2] (wszystkie kombinacje, z wyłączeniem tych, które używają podwójnej krotki);
  4. listę krotek wynikających ze stosów czterech, z krotkami złożonymi przez wzięcie dwóch krotek, obydwu z listy [2] (znowu wszystkie kombinacje, z wyłączeniem tych, które używają podwójnej krotki);

i tak dalej, aż do N. Podczas budowania każdej listy, przycinamy ją zgodnie z Zasada nr 1 powyżej.

Zasada 1b: Ilekroć maksymalna siła jest aktualizowana, wszystkie istniejące listy powinny być przycięte z krotek, które mają siłę mniejszą lub równą nowemu maksimum. Można to zrobić albo natychmiast, albo leniwie, za każdym razem, gdy te krotki są napotykane jako część komponowania nowych krotek.

Jeśli chodzi o opis algorytmu, myślę, że to jest to.

Jeśli chodzi o implementację, przechowuję rzeczywiste krotki jako std::tuple lub struct, z niespodzianką: dla każdej wynikowej krotki musisz zapisać listę pierwotnych krotek, z których została zbudowana; Użyłbym a std::vector<std::size_t> do tego (zawierające indeksy podstawowych krotek z pierwszej listy), jak możesz wtedy użyć std::find_first_of aby wykluczyć kombinacje, które używają podstawowej krotki dwa razy lub nawet lepiej, jeśli utrzymujesz listę posortowaną, std::set_intersection.

Dla list na każdym poziomie, std::vector także.

Rzeczywisty kod C ++ to oczywiście twoja praca.


Uwaga: Algorytm opisany tutaj ma bardzo złe cechy najgorszego przypadku. Najgorszy przypadek dla tego rozwiązania oznacza: duży N, duży H, małe krotki wzrost w porównaniu do H, małe krotki w porównaniu do ich mocnych stron. W takim scenariuszu żadne z przycinania opisanego w powyższym przepisie nie może się rozpocząć do bardzo późnego czasu i do tego momentu mamy kombinatoryczną eksplozję.

Jednakże, dla tego, co uważam za bardziej "interesujące" przypadki, z bardziej równomiernym rozkładem wysokości, ciężarów i mocy (podobnym do podanego przykładu), myślę, że to rozwiązanie byłoby całkiem dobre, nawet w porównaniu z klasycznym dynamicznym rozwiązaniem programistycznym, które w tym przypadku prawdopodobnie byłby to coś w rodzaju rozwiązania z plecakiem całkowitym z jednym odwróconym warunkiem (tak naprawdę to nie przemyślałem).

Wrócę do tego później, kiedy będę miał czas na dokonanie pewnych pomiarów, tylko z ciekawości.


9
2017-12-15 14:54



Udało ci się zrozumieć pytanie i postawić takie serce na odpowiedź. To zasługuje na przegraną ... Szkoda, że ​​mam tylko jeden - Rerito