Atribuição de número de

Dados números modo que há uma atribuição dos números que é uma permutação de modo queA 1 ≤ A 2 ≤ . . . ≤ Um k k Σ i = 1 A i = k ( 2 k + 1 ) i 1 , i 2 , . . . , I 2 k 1 , 2 , . . . , 2 $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$

?

Não consigo encontrar um algoritmo eficiente e que resolva esse problema. Parece ser um problema combinatório. Não foi possível encontrar um problema semelhante ao NP-Complete. Esse problema parece um problema NP-Complete conhecido ou pode ser resolvido com um algoritmo polinomial?

Esse problema é fortemente NP-completo.

Suponha que todos os sejam ímpares. Então sabemos que, como é ímpar, um de e é par e o outro é ímpar. Podemos assumir que é ímpar e é par. Ao permitir e , podemos mostrar que isso é equivalente a pedindo duas permutações, e , dos números tais que .i 2 j - 1 + i 2 j = A j i 2 j - 1 i 2 j i 2 j - 1 i 2 j π j = $A_j$$i_{2j-1} + i_{2j} = A_j$$i_{2j-1}$$i_{2j}$$i_{2j-1}$$i_{2j}$σj=$\pi_j = \frac{1}{2}(i_{2j-1}+1)$πσ1…nπj+σj=$\sigma_j = \frac{1}{2}(i_{2j})$$\pi$$\sigma$$1 \ldots n$$\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$

Esse problema é conhecido por ser NP-completo; veja esse problema de história e este artigo de W. Yu, H. Hoogeveen e JK Lenstra mencionados na resposta.

Aqui está uma dica para você começar: como a soma de todos os números de a é exatamente , uma solução é possível apenas se de fato , e assim por diante . Então, dado , sabemos , e assim por diante. Além disso, .2 k k ( 2 k + 1 ) i 1 + i 2 = A 1 i 3 + i 4 = A 2 i 1 i 2 3 ≤ A j ≤ 4 k - $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$

É um problema de correspondência e, portanto, pode ser resolvido usando o algoritmo de Edmond. Veja a Wikipédia