Witam, moze ktos powiedziec jak to rozwiazac albo jakas podpowiedz, mysle juz pare godzin i nic ciekawego oprocz naiwnego algorytmu mi nie przychodzi do glowy.
0
1
A jaki tu problem? Jest przecież nawet podane jak to rozwiązać - dynamicznie.
Zrób tablicę 0..n w której będziesz zapisywał max wagę sumy przedziałów od 0 do i
Wejściowe interwały sortujesz względem punktu startowego i najlepiej ładujesz do jakiejś mapy.
Wypełnianie tablicy idzie dość prosto:
- iterujemy po kolejnych polach tablicy i=1;i<n
- tablica[i]=0
- dla tablica[i] wartość to maksymalna z wartości tablica[i-(przedziały[j].koniec - przedziały[j].poczatek)] + przedziały[j].waga
gdzie przedziały[] to tablica z przedziałami które kończą się na i-tym elementem i zaczynają przed nim
Skąd tablica[i-przedziały[j].poczatek] + przedziały[j].waga?
tablica[i-(przedziały[j].koniec - przedziały[j].poczatek)] to jest aktualna wartość maksymalna, którą zapamiętaliśmy dla elementów które nie obejmują przedziału który właśnie próbujemy dodać.
Przykładowo dla przedziałów [1,2,3], [1,3,3],[1,2,4] mamy:
tablica[0]=0
tablica[1]=0 (nie ma przedziału kończącego się na '1')
tablica[2]=max[(tablica[2-1] + 3),(tablica[2-1]+4] = 4
tablica[3]=max[tablica(3-2)+3] = 3
I widzimy że przedział 0..3 możemy objąć maksymalnie z wagą sumaryczną 4
Trzeba by do tego dopisac zapamiętywanie które przedziały daly nam "maksymalną wartość" i rozpatrywać sytuacje że może być "dziura"