Pierwsze zadanie polega na tym że najpierw wczytuje n liczb i mam je podzielić na 2 (dodać do 2 zmiennych) tak aby na koniec różnica pomiędzy tymi zmiennymi była jak najmniejsza.
Dla przykładu
Mamy 2 2 2 5
Wynik to 6 i 5
A ten algorytm to ma działać w czasie wielomianowym (np. O(n^100))? ;)
Bo jeśli nie musi, to proste rozwiązanie - sprawdzenie wszystkich możliwości.
Dla każdego elementu w tablicy rozważasz dwie opcje: "element trafia do pierwszej tablicy" oraz "element trafia do drugiej tablicy", a po przyporządkowaniu liczysz różnicę sum.
Złożoność: O(2^n)
A jeśli musi być wielomianowo to powodzenia. Twoje zadanie to klasyczny problem NP-zupełny:
https://en.wikipedia.org/wiki/Partition_problem
There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is NP-hard, but can be solved efficiently in practice.
Są dobre przybliżenia (ale to Ci raczej nie pomoże) oraz algorytmy uzależniające czas wykonania np. od sumy elementów w tablicy, albo algorytmy działające dobrze w praktyce, poszukaj za tym problemem po nazwie, jest sporo tego w sieci.
Drugie zadanie polega na tym że wczytujemy tablicę prostokątną dwuwymiarową liczb dodatnich oraz zmienną oznaczającą bok kwadratu.
Mamy znaleźć maksymalny kwadrat o podanym boku w tej tablicy(czyli taki kwadrat który po zsumowaniu elementów tablicy które obejmuje daje największą wartość).
W wyniku podajemy tą wartość
W drugim wystarczy sprawdzić wszystkie kombinacje:)
I tak i tak musisz sprawdzić wszystkie możliwości jak zapamiętasz po przednie wyniki to nie będzie tak źle ;)
Trochę słabe algorytmicznie rozwiązanie :P.
A odnośnie lepszego: najpierw musisz obliczyć sumę pól dla wszystkich prostokątów z jednym wierzchołkiem w lewym górnym rogu - można to zrobić w czasie O(n).
Czyli z tablicy A:
1 1 1
1 1 1
1 1 1
Otrzymujesz tablicę sum S:
1 2 3
2 4 6
3 6 9
(każde pole to suma elementów powyżej i z lewej strony)
A później możesz obliczyć pole każdego prostokąta w czasie O(1) ((x1+1, y1+1), (x2, y2)) jako S(x2, y2) - S(x2, y1) - S(x1, y2) + S(x1, y1) (rozrysuj sobie)
A kiedy możesz obliczyć pole każdego prostokąta (czyli tez kwadratu) w czasie O(1) to wtedy dopiero można wykonać pętlę po wszystkich możliwościach, w czasie O(n)