Potrzebujesz algorytmu dla tego problemu - algorytmu

Istnieją dwie sekwencje całkowite A [] i B [] o długości N, obie nieposortowane.

Wymaganie: poprzez zamianę elementów między A [] i B [] (może losowo wymieniać, a nie z tym samym indeksem), dokonać różnicy między {sumą wszystkich elementów w A []} i {sumą wszystkich elementów w B [] } być minimum.

PS: Właściwie to jest pytanie z wywiadem, które spotkałem.

Wielkie dzięki

Odpowiedzi:

6 dla odpowiedzi № 1

To będzie NP-trudne! Wierzę, że możesz zrobić redukcję Suma podzbioru do tego.

Zgodnie z komentarzami BlueRaja / polygene postaram się zapewnić pełną redukcję z sumy podzbioru.

Oto redukcja:

Problem z podzbiorem sumy: podane liczby całkowite x₁, x₂, ..., x_n, czy istnieje jakiś niepusty podzbiór, który sumuje się do zera?

Nasz problem: Biorąc pod uwagę dwie liczby całkowite wielkości k, znajdź minimalną możliwą różnicę sumy dwóch tablic, zakładając, że możemy przetasować liczby całkowite w tablicach, traktując obie tablice jako jedną tablicę.

Powiedzmy, że dla naszego problemu mamy czas wielomianowy.

Powiedzmy, że otrzymałeś liczby całkowite T = {x₁, x₂, ..., x_n} (multiset)

Niech S_ja = x₁ + x₂ + ... + x_n + x_ja.

Niech T_ja = {x₁, x₂, ..., x_i-1, x_{i + 1}, ..., x_n } (= T - x_ja)

Definiować

ZA_ja = Tablica utworzona za pomocą T_ja

b_ja = [S_ja, 0, ..., 0] (tzn. Jeden element to S_ja a reszta to zera).

Niech m_ja = minimalna różnica znaleziona przez nasz problem dla tablic A_ja oraz b_ja

(uruchamiamy nasz problem n razy).

Twierdzenie: Niektóre niepuste podzbiory T sumują się do zera wtedy i tylko wtedy, gdy jest jakiś element i, dla którego m_ja = 0.

Dowód: (wlog) powiedz x₁ + x₂ + .. + x_k = 0

Następnie

A = [x_{k + 1}, ..., x_n, 0, ... 0]

B = [x₂, x₃, ..., x_k, S₁, 0, ..0]

daje minimalną różnicę m₁ być | x₂ + .. + x_k + (x₁ + ... + x_n) + x₁ - (x_{k + 1} + .. + x_n) | = | 2 (x₁+ x₂ + .. x_k) | = 0.

Podobnie można udowodnić część if.

Właściwie to również następuje (łatwiej) z partycji: po prostu utwórz nową tablicę ze wszystkimi zerami.

Ostrożnie nie popełniłem żadnych błędów.

---

3 dla odpowiedzi № 2

Weź dowolne wystąpienie NP-kompletne problem podziału:

Podziel multiset A dodatnich liczb całkowitych na dwie wielosety B i C z tą samą sumą

jak₁,za₂,...,za_n}. Dodaj n zer {0,0,0 ..., 0, a₁,...,za_n} i zapytaj, czy zestaw można podzielić na dwa multisety A i B o tej samej sumie i takiej samej liczbie elementów. Twierdzę, że te dwa warunki są równoważne:

• Jeśli A i B są rozwiązaniem problemu, możesz usunąć zera i uzyskać rozwiązanie problemu partycji.
• Jeśli istnieje rozwiązanie problemu z partycją, na przykład a_i1 + a_i2 + ... a_ik = a_j1 + ... + a_{J l} gdzie_i1, a_i2, a_ik, a_j1, ..., a_{J l}} = {a₁, ..., a_n} to oczywiście k + l = n. Dodaj l zer po lewej stronie i k zer po prawej stronie, a otrzymasz 0 + ... + 0 + a_i1 + a_i2 + ... a_ik = 0 + ... + 0 + a_j1 + ... + a_{J l}, który jest rozwiązaniem twojego problemu.

Jest to więc redukcja (więc problem jest NP-trudny), a problemem jest NP, więc jest NP-kompletny.

---

2 dla odpowiedzi nr 3

„sekwencje A [] i B [] o długości N” -> oznacza, że ​​A i B są każdy o długości N?

(Dla jasności używam tablic opartych na 1).

Jeśli tak, to co powiesz na to:

1. Załóżmy, że A [1..N] i B [1..N]
2. Połącz A i B w nową tablicę C o długości 2N: C [1..N] <- A [1..N]; C [N + 1 .. 2N] <- B [1..N]
3. Sortuj C w porządku rosnącym.
4. Weź pierwszy para liczb z C; wyślij pierwszy element (C [1]) do A [1] i drugi element (C [2]) do B [1]
5. Weź drugą parę liczb z C; tym razem wyślij druga element (C [4]) do A [2] i pierwszy element (C [3]) do B [2] (kolejność elementów w parze wysłanej do A i B jest przeciwna do 3)
6. ... powtarzaj 3 i 4, aż skończy się C

Obserwacja tutaj jest taka, że ​​w posortowanej tablicy,sąsiednia para liczb będzie miała najmniejszą różnicę (w porównaniu z parą liczb z pozycji niesąsiadujących). Krok 3 zapewnia, że ​​A [1] i B [1] składają się z pary liczb o możliwie najmniejszej różnicy. Krok 4 zapewnia, że ​​(a) A [2] i B [2] składają się z pary liczb o najmniejszej możliwej różnicy (z dostępnych liczb), a także (b) że różnica jest przeciwna w znaku z kroku 3. Przez kontynuując w ten sposób, zapewniamy, że A [i] i B [i] zawierają liczby z możliwie najmniejszą różnicą. Ponadto, odwracając kolejność, w jakiej wysyłamy elementy do A i B, zapewniamy, że różnica zmienia znak dla każdego kolejnego i.

---

1 dla odpowiedzi nr 4

Spróbuj być chciwym. Biorąc pod uwagę tak ograniczone informacje, nie jestem pewien, co jeszcze można tam umieścić.

---

0 dla odpowiedzi № 5

Nie jestem pewien, czy zapewni to minimalną możliwą odległość, ale pierwszą rzeczą, która przychodzi mi na myśl, jest coś takiego:

int diff=0;
for (int i = 0; i<len; i++){
int x = a[i] - b[i];
if (abs(diff - x) > abs(diff + x)){
swap(a,b,i);
diff-=x;
}else{
diff+=x;
}

}

zakładając, że masz funkcję wymiany, która pobiera dwie tablice i wymienia przedmioty na pozycji i :)

obliczanie i dodawanie różnicy między dwiema wartościami w pozycji i otrzymujesz przyrostową różnicę między sumami elementów dwóch tablic.
na każdym kroku sprawdzasz, czy lepiej jest dodać (a [i] -b [i]) lub (b [i] -a [i]). jeśli b [i] -a [i] to „s” W tym przypadku zamieniasz elementy na pozycji i w tablicach.

Może nie będzie to najlepszy sposób, ale powinien to być początek :)

---

0 dla odpowiedzi № 6

Problem jest NP-Complete.

Możemy zmniejszyć problem podziału do wersja decyzyjna tego problemu, tj. biorąc pod uwagę dwie tablice liczb całkowitych o tym samym rozmiarze, określ, czy elementy można zamienić, aby sumy były równe.

Wejście do problemu partycji: zestaw S liczb całkowitych, o rozmiarze N

Aby przekształcić to wejście w wejście donasz problem, definiujemy A jako tablicę wszystkich elementów w S, a B tablicę o tym samym rozmiarze, z B [i] = 0 dla wszystkich i. Ta transformacja jest liniowa w wielkości wejściowej.

Oczywiste jest, że nasz algorytm zastosowany w A i B zwraca wartość true wtedy i tylko wtedy, gdy istnieje podział S na 2 podzbiory, tak że sumy są równe.

---