[Algorytmy] Czy da się poprawić złożoność czasową?

Marcinek665 · Post autor: **Marcinek665** » 15 gru 2012, o 00:00

Dana jest tablica \(\displaystyle{ 2n}\)-elementowa, w której siedzą liczby całkowite. Mamy napisać algorytm, który sprawdzi, czy spośród elementów tej tablicy da się wybrać taki podzbiór \(\displaystyle{ n}\)-elementowy, by jego suma była równa sumie elementów niewybranych.

Mój pomysł był taki, by wysumować całą tablicę. Dostaniemy wtedy jakąś sumę \(\displaystyle{ S}\). Nasz problem sprowadza się zatem do rozstrzygnięcia, czy istnieje taki podzbiór \(\displaystyle{ n}\) elementowy, którego suma wynosi \(\displaystyle{ \frac{S}{2}}\). Ale tutaj nie mam kompletnie żadnego pomysłu, jak to zrobić w jakiejś rozsądnej złożoności czasowej.

Proszę, w miarę możliwości, o same wskazówki, a nie całe rozwiązania.

Pozdrawiam

abc666 · Post autor: **abc666** » 15 gru 2012, o 12:50

Marcinek665 · Post autor: **Marcinek665** » 19 gru 2012, o 15:03

A gdybyśmy zmodyfikowali problem na następujący:

dla ciągu \(\displaystyle{ 2n}\) elementowego rozstrzygnąć, czy da się wybrać tak podciąg \(\displaystyle{ n}\) elementowy, by podciągi wybrany i niewybrany były takie same (kolejność jest istotna).

gryxon · Post autor: **gryxon** » 19 gru 2012, o 18:56

Mam pewien pomysł ale nie wiem czy wyjdzie z tego coś sensownego. Jak nie chcesz całego algorytmu na tacy to poczekaj aż zaklepie i sprawdze czy jakoś działa ; ].
Ogólnie założenie mam takie że próbuje generować dwa takie ciągi, a na końcu sprawdzam czy są równej długości.

EDIT: Chyba będzie działać...
wskazówka(implementacyjna)

Ukryta treść:

wskazówka 2(algorytmiczna):

Ukryta treść:

Marcinek665 · Post autor: **Marcinek665** » 19 gru 2012, o 19:45

\(\displaystyle{ 1, 1, 2, 3, 3, 2.}\)

Z Twojego algorytmu wynika, że się da wybrać żądany podciąg (bo utworzyliśmy ciągi złożone z \(\displaystyle{ 1, 2, 3}\)), ale wybrać ich się nie da, bo kolejność się nie zgadza.

Czy może źle rozumiem?

Panda · Post autor: **Panda** » 19 gru 2012, o 19:47

Anyway \(\displaystyle{ 1,1,2,1,1,2}\) - taktyka z dawaniem dwóch kolejnych takich samych do dwóch różnych ciągów tu nie działa. Chyba, że chodzi o coś innego we wskazówce drugiej?

Problem trochę mi przypomina ten postawiony w
... miwojazer/ .
Dynamiczny algorytm kwadratowy jest bardzo podobny - stanem jest \(\displaystyle{ P(i,k)}\), który przyjmuje \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) w zależności od tego, czy można prefiks długości \(\displaystyle{ i}\) podzielić na ciąg długości \(\displaystyle{ k}\) i drugi "taki sam" (w sensie, krótszy jest prefiksem dłuższego) długości\(\displaystyle{ i-k}\).
\(\displaystyle{ P(i,k)=1}\),jeśli \(\displaystyle{ k \le n}\) oraz (\(\displaystyle{ P(i-1,k-1) = 1}\) i można za pomocą \(\displaystyle{ T}\) przedłużyć pierwszy ciąg, lub jeśli \(\displaystyle{ P(i-1,k)=1}\) i można przedłużyć drugi).

gryxon · Post autor: **gryxon** » 19 gru 2012, o 19:58

Kolejka panowie, kolejka...
Kontener FIFO.

EDIT: Jak chcecie moge przedstawić cały swój algorytm.

Cały algorytm:

Ukryta treść:

Panda · Post autor: **Panda** » 19 gru 2012, o 20:06

Wiemy co to jest kolejka
Chętnie zobaczę cały algorytm (ale najlepiej opis, szkic, nie kod )

gryxon · Post autor: **gryxon** » 19 gru 2012, o 20:07

Wkleiłem do poprzedniego postu.
Sorry za ewentualne błędy .

royas · Post autor: **royas** » 19 gru 2012, o 20:09

Mały lecz znaczący błąd
"Dodajemy element ciągu do Ciągu A. i kolejki"

gryxon · Post autor: **gryxon** » 19 gru 2012, o 20:11

Dokładnie, dziękuje za znalezienie "literówki";)

Panda · Post autor: **Panda** » 19 gru 2012, o 20:26

W skrócie:
Jeśli element \(\displaystyle{ t}\) może pomóc ciągowi \(\displaystyle{ B}\) dogonić ciąg \(\displaystyle{ A}\), to go dodaj do \(\displaystyle{ B}\), jeśli nie, to dodaj do \(\displaystyle{ A}\).
A czy to się nie wyłoży dla

Kod: Zaznacz cały

caabbcabbaabbabb

?
Powiem od razu że prawidłowy wynik to \(\displaystyle{ A=B=caabbabb}\), tymczasem, parę pierwszych kroków generuje - moim zdaniem - \(\displaystyle{ (A,B)=(caabb,c)}\), a potem \(\displaystyle{ (A,B)=(caabb,ca)}\), i tu się zacina, bo to zły wybór..

gryxon · Post autor: **gryxon** » 19 gru 2012, o 20:33

Nie da się wybrać takiego ciągu z twojego przypadku chyba...

Edit: sorry może jednak da ; >, zaraz ogarne bo chwilowo nie mam czasu.

Panda · Post autor: **Panda** » 19 gru 2012, o 20:35

W sensie, że nie da się

Kod: Zaznacz cały

caabbabb

? No jak to nie Ciąg \(\displaystyle{ b}\) to drugie \(\displaystyle{ c}\) plus sufiks.

gryxon · Post autor: **gryxon** » 19 gru 2012, o 20:45

To narazie wychodzi na to że napisałem heure ; >.
Jak przyjde do domu to jeszcze pomyśle .