Pomoc w zadaniu c++, strona cses.fi

pytanie zadane 27 sierpnia 2020 w C i C++ przez gryzedywany Użytkownik (510 p.)

Hejka mam problem z tym zadaniem. Zupełnie nie mam pomysłu jak się do niego zabrać. Czy mógłby mi ktoś dać wskazówkę jak to ugryźć?

There are nn apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.
Example
Input:
5
3 2 7 4 1
Output:
1
Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8).

Wiem, że muszę dążyć żeby waga jednego zestawu była jak najbardziej zbliżona do wagi całości podzielonej przez dwa. Na początku myślałam żeby tworzyć wszystkie możliwe zestawy i zapamiętywać ten najcięższy (ale mniejszy lub równy połowie) jednak nie wydaje mi się to dobre rozwiązanie.

Z góry dzięki za pomoc <3

1	komentarz 27 sierpnia 2020 przez Whistleroosh Maniak (56,980 p.) Jezeli to jest to zadanie gdzie n jest mniejsze od 20 to dobrze myślałaś. Trzeba sprawdzić wszystkie możliwe podziały i najłatwiej zrobić to maskami bitowymi

komentarz 27 sierpnia 2020 przez gryzedywany Użytkownik (510 p.)

Tak n jest mniejsze od 20, a masz może jakieś linki do materiałów na temat tych masek bitowych? Najlepiej z ich zastosowaniem. O operacjach bitowych czytałam trochę na tej stronie: http://cpp0x.pl/kursy/Kurs-C++/Poziom-5/Operacje-bitowe/597 . Teorię mniej więcej zrozumiałam ale nie umiem tego jeszcze zastosować :/