Tugas nomor

Diberi angka sedemikian rupa sehingga apakah ada penetapan angka yang merupakan permutasi dari sedemikian rupaA 1 ≤ A 2 ≤ . . . ≤ A 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$

?

Saya tidak dapat menemukan algoritma yang efisien dan yang menyelesaikan masalah ini. Tampaknya menjadi masalah kombinatorial. Saya tidak dapat menemukan masalah NP-Complete yang sama. Apakah masalah ini terlihat seperti masalah NP-Complete yang diketahui atau dapatkah dipecahkan dengan algoritma polinomial?

Masalah ini sangat lengkap dengan NP.

Misalkan semua aneh. Maka kita tahu bahwa karena adalah ganjil, salah satu dari dan adalah genap dan yang lainnya ganjil. Kita dapat mengasumsikan bahwa aneh dan adalah genap. Dengan membiarkan dan , kita dapat menunjukkan bahwa ini setara dengan meminta dua permutasi, dan , dari angka sehingga .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}$$\pi_j = \frac{1}{2}(i_{2j-1}+1)$$\sigma_j = \frac{1}{2}(i_{2j})$$\pi$$\sigma$$1 \ldots n$$\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$

Masalah ini dikenal sebagai NP-complete; lihat masalah cstheory.se ini dan makalah W. Yu, H. Hoogeveen, dan JK Lenstra ini dirujuk dalam jawabannya.

Berikut ini adalah petunjuk untuk memulai: karena jumlah semua angka dari hingga 2 k adalah tepat k ( 2 k + 1 ) , solusinya hanya mungkin jika faktanya i 1 + i 2 = A 1 , i 3 + i 4 = A 2 dan seterusnya. Jadi mengingat saya 1 kita tahu saya 2 , dan seterusnya. Juga, 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$

Ini masalah yang cocok, dan bisa diselesaikan dengan menggunakan algoritma Edmond. Lihat wikipedia