Cóż mogę rzec. Nie rozwiązałem tego zadania więc nie mogę wypowiadać się z pozycji eksperta 
Ale jeżeli poszukujesz wskazówek...
Pomysł jest taki. Ja napiszę co widzę w taki sposób w jaki rzeczywiście układa mi się wizja tego zadania w głowie. Bez zbędnych upiększeń, dbałości o gramatykę i liczne przykłady. Być może niewiele zrozumiesz z tej wypowiedzi, ale właśnie o to chodzi Każdą rzecz której nie rozumiesz możesz wygooglować albo znaleźć w jakiejś książce. Nota bene pewną część tej wizji już znasz z mojego poprzedniego postu. Zauważ też, że nie rozwiązałem tego zadania i być może moje rozumowanie nie jest prawidłowe, co dostrzegłbym (albo i nie) dopiero po wczytaniu się w treść i próbie stworzenia dobrego algorytmu
Wiemy, że SPOJ to tylko i aż SPOJ. Tylko - zadania które tu występują mogą wydawać się piekielnie trudne, ale w rzeczywistości nie wymagają żadnej wielkiej i abstrakcyjnej wiedzy. Aż - wiele osób posiadających wielką i abstrakcyjną wiedzę nie ma szans z wieloma zadaniami średnimi, a pewne problemy mogą im sprawić również zadania łatwe. W gruncie rzeczy SPOJ to kwestia wprawy i oczywiście chęci poświęcenia czasu na jakiś problem Wniosek - rozwiązania zadania nie należy szukać w najnowszych osiągnięciach matematyki teoretycznej tylko w czymś znanym.
Przedmiotów jest zaledwie 100, a pojemności plecaków to 500. Ogólnie autor operuje bardzo małymi liczbami, a ilość testów jest znana i wynosi 1 - każdy przykład stanowi samodzielny test. Odnotowane fakty nie miałyby znaczenia gdyby nie to, że - jak pisałem w poprzednim akapicie - to jest SPOJ. Na podstawie specyfikacji zadania można oszacować złożoność czasową wzorcówki (rozwiązania wzorcowego). Bierzemy sobie np to http://www-users.mat.umk.pl/~stencel/acm/algorytmika_praktyczna.pdf21 i patrzymy na rozdział 9. Okazuje się, że nasz program z dużą dozą prawdopodobieństwa powinien mieć złożoność O(n^3), co jest bardzo użytecznym wnioskiem!
Jednocześnie w podanej pozycji napisano, że w tej klasie rozwiązań znajdują się zazwyczaj problemy rozwiązywalne metodą programowania dynamicznego. Czy ma to sens? Znowu - wracamy do tego, że SPOJ to SPOJ. Jedną z cech SPOJa jest to, że ma uczyć. Autorzy nie tworzą zadań by pokazać jacy są mądrzy a po to, by pomóc innym ludziom nauczyć się algorytmów i programowania. Z tego powodu nieraz w treści zadania znajduje się jakaś podpowiedź - nazwa algorytmu, aluzja do jakiegoś problemu matematycznego, a nawet nazwa typu zmiennej w jakimś języku programowania, której zastosowanie jest kluczowe w celu rozwiązania. Możesz też spotkać się z fragmentami kodu, które trzeba uzupełnić i innymi tego rodzaju podpowiedziami. Czy w tym zadaniu jest podpowiedź? Tak! Jest nią słowo plecak, które prowadzi do dyskretnego problemu plecakowego, który z kolei jest problemem optymalizacyjnym rozwiązywalnym w czasie O(2^n) brutem (brute force algorithm, algorytm naiwny, algorytm brutalny, podejście brutalne, algorytm siłowy, podejście siłowe, ...), ale metodą programowania dynamicznego można go rozwiązać w czasie wielomianowym O(n^2). Stwierdzenie, że zadanie ma coś wspólnego z plecakami jest bezcennym wnioskiem!
Przerwa od analizy zadania Jako ciekawostkę mogę Ci powiedzieć, że Twoje podejście było niezłe. Podwójnie niezłe. Po pierwsze, prawidłowo rozwiązałeś / prawie prawidłowo rozwiązałeś (nie mam kodu więc głowy nie dam) pewną szczególną podklasę problemów plecakowych, dla których metoda zachłanna prowadzi do znalezienia optimum. Po drugie, podałeś całkiem dobry algorytm aproksymacyjny dla dużej części innych podklas problemów plecakowych. Wracamy do analizy zadania
Wiemy, że zadanie stanowi zmodyfikowaną i rozszerzoną wersję problemu plecakowego. W związku z tym należy się zapoznać z tym problemem, przeanalizować go i zaproponować rozwiązanie zadania pamiętając, że najprawdopodobniej autor chciałby solucję o złożoności obliczeniowej około O(n^3). Oczywiście limit czasu wynoszący 10 sekund może sugerować, że w istocie chodzi nawet o jakieś O(n!), O(2^n) itd, ale to wyjdzie w praniu - na pewno nikt nie oczekuje od Ciebie arcyszybkiego programu podającego odpowiedź jeszcze przed wczytaniem danych albo programu, który miliardy przedmiotów zapakuje w odpowiedni sposób w czasie kilku milisekund Słowem plecaki + programowanie dynamiczne vs zachłanne + wysiłek własny powinny prowadzić albo do AC albo do pomysłu na program, który uzyska AC
PS
Zauważ, że zadanie na maksa (100.0) rozwiązało dużo mniej osób, bo 55.
Apr '17
Aug '17
