Przypisanie numeru

Biorąc pod uwagę liczb tak, że istnieje przypisanie liczb który jest permutacją taki, żeA 1 ≤ A 2 ≤ . . . ≤ A k k $k$$A_1 \leq A_2 \leq ... \leq A_k$$\sum\limits_{i=1}^k A_i = k(2k + 1)$$i_1, i_2, ... , i_{2k}$$1, 2, ... , 2k$

$i_1 + i_2 \leq A_1\\ i_3 + i_4 \leq A_2\\ .\\.\\.\\ i_{2k-1} + i_{2k} \leq A_k$

?

Nie mogę znaleźć wydajnego algorytmu, który rozwiązuje ten problem. Wydaje się, że jest to problem kombinatoryczny. Nie udało mi się znaleźć podobnego problemu z NP-Complete. Czy ten problem wygląda jak znany problem NP-Complete, czy można go rozwiązać za pomocą algorytmu wielomianowego?

Ten problem jest całkowicie NP.

Załóżmy, że wszystkie j są dziwne. Wiemy zatem, że skoro i 2 j - 1 + i 2 j = A j jest nieparzysta, jeden z i 2 j - 1 i i 2 j jest parzysty, a drugi jest nieparzysty. Możemy założyć, że i 2 j - 1 jest nieparzysta, a i 2 j jest parzysta. Pozwalając π j = 1$A_j$$i_{2j-1} + i_{2j} = A_j$$i_{2j-1}$$i_{2j}$$i_{2j-1}$$i_{2j}$iσj=$\pi_j = \frac{1}{2}(i_{2j-1}+1)$, możemy pokazać, że jest to równoważne z prośbą o dwie permutacje,πiσ, liczb1…ntakich, żeπj+σj=$\sigma_j = \frac{1}{2}(i_{2j})$$\pi$$\sigma$$1 \ldots n$.$\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$

Ten problem jest znany jako NP-zupełny; zobacz ten problem z cstheory.se oraz artykuł W. Yu, H. Hoogeveen i JK Lenstry, do których odwołuje się odpowiedź.

Oto wskazówka na początek: ponieważ suma wszystkich liczb od do 2 k wynosi dokładnie k ( 2 k + 1 ) , rozwiązanie jest możliwe tylko wtedy, gdy w rzeczywistości i 1 + i 2 = A 1 , i 3 + i 4 = A 2 i tak dalej. Tak więc biorąc pod uwagę i 1 wiemy i 2 , i tak dalej. Również 3 ≤ A j ≤ 4 k - 1 .$1$$2k$$k(2k+1)$$i_1 + i_2 = A_1$$i_3 + i_4 = A_2$$i_1$$i_2$$3 \leq A_j \leq 4k-1$

Jest to pasujący problem, dlatego można go rozwiązać za pomocą algorytmu Edmonda. Zobacz wikipedia