[Snori]

Mam napisać algorytm wykorzystujący programowanie dynamiczne albo algorytm zachłanny, aby znaleźć podzbiór rezerwacji dla dwóch apartamentów. Jako dane wejściowe mam podaną liczbę rezerwacji, a następnie w kolejnych liniach po trzy liczby całkowite oznaczające kolejno dzień początkowy rezerwacji, dzień końcowy oraz ewentualny zysk. Na wyjściu ma zostać wypisany maksymalny możliwy zysk.
5 //5 rezerwacji
9 11 2 //pierwsza rezerwacja od dnia 9 do dnia 11 (zapłata 2)
1 5 4
1 8 7
5 9 4
6 10 5
Output: 18
- to przykładowe dane wejściowe.
Napisałem algorytm, który najpierw znajduje optymalny podzbiór dla jednego apartamentu, potem odejmuje wykorzystane rezerwacje i następnie znowu znajduje optymalny podzbiór dla pozostałych, ale niestety działa to dobrze tylko dla niektórych danych. Może ktoś ma jakiś pomysł albo mógłby mi podlinkować coś podobnego bo już trzeci dzień nad tym siedzę i nic lepszego mi nie przychodzi do głowy.

#programowanie #java #cpp #algorytmy #naukaprogramowania

[MamCieNaHita]

@Snori: skąd wiesz, że działa dobrze tylko dla niektórych danych? jeżeli potrafisz policzyć "na kartce", to czym się różni algorytm "na kartce" od tego w kodzie?

[Snori]

@MamCieNaHita: Działa dobrze dla małych danych. Ale mam też plik które mają np. 100 rezerwacji i dla nich jest już zły wynik. Liczenie tego na kartce dla tak dużych danych zajęłoby mi kilka godzin o ile bym się nie pomylił po drodze.

[Vetinari]

@Snori: Okej, ale skąd w takim razie wiesz, że dla 100 rezerwacji jest źle?

[Snori]

@Vetinari: Mamy podane odpowiedzi do każdych danych.

[Lodomir1337]

@Snori: Twój algorytm jest niepoprawny. Wyobraź sobie takie dane
4
1 2 10
9 10 10
2 10 2
1 9 2
Optymalny wynik to 24 a Twój algorytm daje 22

[Snori]

@Lodomir1337: No właśnie tu jest problem. Nie wiem jak to zrobić, aby dla każdych danych był dobry wynik. Napisałem program generujący wszystkie możliwości, ale on już dla 15 rezerwacji nie wyrabia, bo jest za duża złożoność(3^liczby rezerwacji).

[Lodomir1337]

@Snori: a próbowałeś zrobić coś w stylu dynamicznego rozwiązania problemu plecakowego dla dwóch plecaków?