Dwa równe zbiory

[thx4]

Witam

czy jest jakaś możliwość sprawdzenia przed faktycznym podziałem czy dany zbiór można podzielić na dwa równe zbiory? Nie ważne które elementy ważne czy się da czy nie.

Sprawdzanie sumy wartości poszczególnych elementów zbioru modulo mam ale np. 10 10 10 10 10 nie da się podzielić a modulo wychodzi 0

[bartek118]

Zbioru nie można podzielić na dwa równe, bo każdy jego element jest w nim dokładnie raz, a zbiory są równe jeśli mają te same elementy. Wyjątkiem jest zbiór pusty.

[thx4]

Nie chodziło mi o zbiór w sensie stricte, po prostu grupa liczba, worek liczb, zgrupowanie liczb, wszystko jedno. Mam grupę liczb i chciałbym przed faktycznym podziałem na dwie grupy liczb zobaczyć czy się da je podzielić tak żeby po podziele sumy wartości jednej i drugiej podgrupy były sobie równe. Przykłady:

10, 10, 10, 10, 10 - 50 mod 2 = 0 ale nie da się ich podzielić, trzeba by jedną 10 rozerwać a nie można
17, 13, 10, 15, 2 - 57 mod 2 = 1 nie da się
40, 19, 18, 13, 10, 10, 10, 10, 10 - da się, 40, 10, 10, 10 i 19, 18, 13, 10, 10
3, 8, 4, 1, 5, 13 - da się, 13, 4 i 8 5 3 1

Czy jest jakaś metoda na zobaczenie czy da się tak podzielić

[Xitami]

to "tylko" \(\displaystyle{ 2^{n-1}}\) możliwości

[abc666]

thx4, suma oczywiście musi być parzysta. Potem dzielisz ją przez dwa i próbujesz uzyskać taką sumę z elementów. Możesz to sobie robić zachłannie.

[Zordon]

Wydaje się, że to jest NP-zupełne. Można rozwiązać to algorytmem plecakowym.

[thx4]

Rozwiązane ma to za pomocą algorytmu z nawrotami. Chodziło mi tylko o to czy jest możliwość sprawdzanie czy da się podzielić bez wcześniejszego liczenia za pomocą konkretnego algorytmu.

Czyli np. dla 10, 10, 10, 10, 10 da się jakoś sprawdzić że to tego nie da się podzielić czy trzeba liczyć za pomocą algorytmu i wtedy już wyjdzie że się nie da.

[Zordon]

Jak pisałem, taki problem decyzyjny jest (o ile się nie mylę) NP-trudny, co oznacza mniej więcej tyle, że nie da się tego łatwo sprawdzać

[Piotr Pstragowski]

Ten problem jest NP-trudny. Pokażę to przez sprowadzenie do niego problemu Sumy podzbioru, którego NP-trudność jest pokazana tu - (Twierdzenie 4.2).

Załóżmy, że mamy tablicę liczb \(\displaystyle{ a_i}\) i niech \(\displaystyle{ B}\) oznacza szukaną wartość sumy podzbioru. Niech

\(\displaystyle{ Z = \sum_{i} a_i}\)

i zakładam, że \(\displaystyle{ B \leq Z}\). Połóżmy:

\(\displaystyle{ b_1 = 5Z - B, \ b_2 = 4Z+B}\)

Jest teraz jasne, że oryginalny problem ma rozwiązanie wtedy i tylko wtedy, gdy tablica liczb \(\displaystyle{ a_1, a_2, ..., a_n, b_1, b_2}\) daje się podzielić na dwie równe połowy. (Zauważmy, że \(\displaystyle{ b_1, b_2}\) musiałyby być w różnych połowach.)

Pokazałem więc, że Twój problem jest nieprostszy od problemu sumy podzbioru, jest więc NP-trudny.

To znaczy mniej więcej tyle, że ludzkość nie zna żadnych dobrych sposobów rozwiązywania takich problemów, a gdyby poznała, to najmniej połowa informatyków byłaby mocno zdziwiona.