Zadanie pakowanie plecakowe

Adrian chce zostać lepszym sportowcem, więc postanowił spędzić na bieżni dokładnie N (1 ≤ N ≤ 10000)
minut. Podczas każdej minuty może wybrać czy chce biec, czy odpoczywać.
Ostateczna odległość jaką Adrian przebiegnie zależy jednak od jego ’współczynnika zmęczenia’, który początkowo wynosi 0. Jeżeli podczas i-tej minuty zdecyduje się biec, przebiegnie odległość równą Di (1 ≤ Di ≤
1000), a jego współczynnik zmęczenia zwiększy się o 1. Współczynnik ten nie może jednak przekroczyć M
(1 ≤ M ≤ 500). Jeżeli jednak Adrian w i-tej minucie zdecyduje się odpocząć, jego współczynnik zmęczenia
zmaleje o 1. Adrian nie może ponownie powrócić do biegu dopóki jego współczynnik zmęczenia nie wyniesie
0. Gdy wynosi on 0, Adrian może zdecydować się odpocząć albo biec.
Pod koniec N minutowego treningu współczynnik zmęczenia musi wynosić dokładnie 0, w przeciwnym wypadku Adrian nie będzie miał wystarczająco dużo sił na dalszą część dnia!
Znajdź maksymalną odległość jaką Adrian może przebiec.

Wejście
Dwie liczby całkowite oddzielone spacją: N oraz M. Kolejnych N linii zawiera jedną liczbę całkowitą: Di
.
Wyjście
Jedna liczba całkowita oznaczająca największą odległość jaką Adrian może przebiec, spełniając powyższe
warunki.

Przykład
Dla danych wejściowych:
5 2
5
3
4
2
10

poprawnym wynikiem jest:
9

Uwaga:
Adrian biegnie w trakcie pierwszej minuty (odległość = 5), odpoczywa podczas drugiej, biegnie podczas trzeciej
(odległość=4) i odpoczywa podczas czwartej i piątej. Zauważ, że Adrian nie może biec podczas piątej minuty,
ponieważ nie skończył by swojego treningu ze współczynnikiem zmęczenia równym 0.

Moj Przykład
Dla danych wejściowych:
8 3
6
9
7
6
8
3
1
2

poprawnym wynikiem jest:
27

mam problem z tym zadaniem nie bylem na jego omownieniu a teraz mam problem zeby nadrobic. Nie chce gotowego kodu tylko wskazowke jak to mozna zrobic a i chcialbym
dodac ze to moj pierwszy post na tym forum wiec jesli popelnilem jakies bledy to nie linczujcie

Spróbuj szukać rozwiązania zadania od tyłu - skoro i tak będzie musiał odpocząć pod koniec, by zmęczenie spadło do 0, będziesz miał dzięki temu gwarancję poprawności rozwiązania, nawet, jeśli nie będzie najlepsze to przynajmniej będzie poprawne - zauważ, że skoro w każdej minucie może albo ćwiczyć, albo odpoczywać, to wszystkich kombinacji (łącznie z błędnymi) jest aż 2^N ;) To jest wręcz zaporowa ilość, gdy N przekroczy powiedzmy 2³⁰-2⁴⁰, nie mówiąc o 2¹⁰⁰⁰.

Szukając prawidłowego rozwiązania będziesz musiał zbudować serię biegów i odpoczynków różnej długości - możesz wykorzystać np. algorytm zachłanny i dla m=1...M sprawdzać, jaka długość odpoczynku / biegu pozwoli najlepiej wykorzystać 2*m czasu treningu przeznaczonego na daną serię. W tym celu przyjmujesz jakąś heurystykę - może to być np.

• stosunek przebiegniętego dystansu do długości serii
• stosunek potencjału wykorzystanego na bieganie (suma Di w biegu) do potencjału "zmarnowanego" na odpoczynek (suma Di w spoczynku)

Zwiększasz m tak długo, jak długo opłaca się wydłużyć serię (rośnie wartość heurystyki). W momencie, gdy np. kolejny krok zmniejszy "wydajność" biegania, przerywasz serię i zaczynasz generowanie jej od nowa :)

Dla większych N algorytm zachłanny prawie na pewno nie da Ci najlepszego możliwego wyniku, a jedynie jakieś rozwiązanie przybliżone - może być całkiem bliskie najlepszemu, a może być zupełnie z czapy.

Możesz też zaszaleć i spróbować sił z algorytmami ewolucyjnymi - ale podobnie jak Ty nie byłem na omówieniu tego zadania i nie wiem, jakie techniki dopuszcza Twój prowadzący :P

Chcąc opracować taki algorytm heurystykę masz już podaną (przebiegnięty dystans), wystarczy jedynie ustalić sposób przechowywania danych (np. długość poszczególnych etapów biegu/odpoczynku, jakieś reguły mutowania/krzyżowania i np. funkcje kary do zapobiegania generowaniu błędnych kombinacji - algorytmy ewolucyjne generalnie opierają się na przypadkowych zmianach i krzyżowaniu ze sobą "osobników" w celu znajdowania coraz lepszych rozwiązań :) Ale tutaj nie dość, że znowu nie dostaniesz zapewne optymalnego rozwiązania, to jeszcze dochodzi kwestia przypadkowości - możesz zapuścić taki algorytm 100 razy i dostać 100 różnych rezultatów :P