Diberikan multiset dari bilangan asli X, pertimbangkan sekumpulan semua jumlah yang mungkin:

$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$

Misalnya, sementara .$\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}$$\textrm{sums}(\left\{1,1\right\}) = \left\{0, 1, 2\right\}$

Apa algoritma yang paling efisien untuk menghitung operasi terbalik (diukur dalam ukuran ukuran input jumlah)? Secara khusus apakah mungkin untuk menghitung secara efisien salah satu dari yang berikut:

1. Apakah set yang diberikan adalah set jumlah yang valid. (Misalnya, valid tetapi tidak.)$\left\{0,1,2\right\}$$\left\{0,1,3\right\}$
2. Multiset yang menjumlahkan set yang diberikan.
3. The terkecil multiset yang jumlah ke set yang diberikan. (Misalnya, dan keduanya sama dengan tetapi yang pertama lebih kecil.)$\left\{1,2\right\}$$\left\{1,1,1\right\}$$\left\{0,1,2,3\right\}$

Larutan

Solusi memiliki dua bagian. Pertama kita menemukan set minimal, maka kita membuktikan bahwa itu dapat mewakili set jumlah daya. Solusinya disesuaikan untuk implementasi pemrograman.

Algoritma set minimal

1. Temukan elemen maksimal dari jumlah (multi) set. , set minimal potensial (multi) awalnya kosong.$a_{m}$$P$

2. Kecuali hanya ada satu grup, dalam semua cara yang mungkin sebagai pasangan jumlah yang berjumlah hingga , a m S i j = { ( a i , a j ) | a i + a j = a m$a_{m}$$a_{m}$$S_{ij}=\{(a_{i},a_{j})|a_{i}+a_{j}=a_{m}\}$

3. Periksa bahwa semua elemen dari himpunan jumlah disertakan.

4. Temukan elemen maksimal dari semua (artinya bersama) dengan properti berikut: untuk setiap , ada di , atau kita dapat menemukan dari himpunan jumlah sehingga ada di . S i j S i j a s S i j a p a p + a s S i $a_{s}$$S_{ij}$$S_{ij}$$a_{s}$$S_{ij}$$a_{p}$$a_{p}+a_{s}$$S_{ij}$

5. Jika itu adalah tidak mengandung , cukup jumlah , hapus dari (atau atur saja tanda untuk mengabaikannya) dan masukkan dan di sebagai gantinya.$S_{ij}$ a s + a p a p + a s S i j a p a s S i $a_{s}$$a_{s}+a_{p}$$a_{p}+a_{s}$$S_{ij}$$a_{p}$$a_{s}$$S_{ij}$

6. Jika suatu elemen ada di setiap hapus elemen itu dari semua satu kali (atau cukup tetapkan tanda untuk mengabaikannya dan tidak menyentuhnya lagi) dan tambahkan ke daftar elemen-elemen potensial minimal set . S i j$S_{ij}$$S_{ij}$$P$

7. Ulangi sampai semua kosong$S_{ij}$

8. Jika beberapa tetap tidak kosong dan kami tidak dapat melanjutkan, coba lagi dengan nilai maksimum dari semua . S i $S_{ij}$$S_{ij}$

9. Menciptakan langkah-langkah rekursif tanpa kepindahan dan lanjutkan dengan algoritma cakupan kekuasaan set atas . (Sebelum ini, Anda dapat melakukan pemeriksaan dengan aman bahwa menyertakan semua elemen yang tidak dapat direpresentasikan sebagai jumlah dari dua elemen sehingga pasti harus berada di set yang mendasarinya. Misalnya, elemen minimal harus dalam )P $P$$P$$P$

(10. Amati bahwa solusi set minimal yang merupakan tujuan dari algoritma tidak dapat berisi lebih dari satu pengulangan dari nomor yang sama.)

Contoh:

$$\{2,3,5,7,8,10,12,13,15\}$$

Mewakili 15 dalam semua cara yang mungkin sebagai jumlah dari dua angka dari himpunan jumlah.

$$(13,2),(12,3),(10,5),(8,7)$$

Cobalah untuk menemukan angka maksimal yang ada di semua grup atau yang dapat direpresentasikan sebagai jumlah. Jelas kita bisa mulai mencarinya dari 8, tidak ada gunanya naik di atasnya.

13 dari kelompok pertama adalah 13 = 8 + 5 jadi 13 baik-baik saja, tetapi 12 dari kelompok kedua tidak baik karena tidak ada 4 untuk membuat 12 = 8 + 4 dalam himpunan jumlah. Selanjutnya kita coba dengan 7. Tapi segera 13 tidak bisa ditutup, tidak ada 6.

Selanjutnya kita coba 5. 13 = 5 + 8, 12 = 5 + 7, 10 = 5 + 5, dan untuk yang terakhir 8 = 5 + 3 atau 7 = 5 + 2 tetapi tidak keduanya. Grup sekarang:

$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$

5 berulang di semua grup sehingga kami mengekstraknya . Kami mengekstrak 5 hanya sekali dari masing-masing kelompok.$P=\{5\}$

$$(8,2),(7,3),(5,5),(3,7)$$

Jelas tidak ada poin lebih tinggi dari 5 jadi kami mencoba 5 lagi. 8 = 5 + 3, 7 = 5 + 2, jadi semuanya baik-baik saja

$$((5,3),2),((5,2),3),(5,5),(3,(5,2))$$

Ekstrak satu 5 lagi dari semua kelompok karena berulang. (Ini tidak umum tetapi kasus kami sengaja dibuat untuk menampilkan apa yang harus dilakukan jika kami memiliki pengulangan.)$P=\{5,5\}$

$$(3,2),(2,3),(5),(3,2)$$

Sekarang kita coba dengan 3 dan memiliki 5 = 3 + 2. Tambahkan ke grup.

$$(3,2),(2,3),(3,2),(3,2)$$

Sekarang ekstrak 3 dan 2 karena mereka berulang di mana-mana dan kami baik-baik saja dan grup kosong.$P=\{5,5,3,2\}$

$$(),(),(),()$$

Sekarang, kita perlu membuat ulang langkah-langkah rekursif tanpa pemindahan, ini berarti melakukan hal di atas tanpa benar-benar menghapus elemen dari hanya menempatkannya di dan menandai untuk tidak mengubahnya lagi.$S_{ij}$$P$

( ( 5 , 8 ) , 2 ) , ( ( 5 , 7 ) , 3 ) , ( ( 5 , 5 ) , 5 ) , ( ( 5 , 3 ) ,

$$(13,2),(12,3),(10,5),(8,7)$$ ( ( 5 , ( 5 , 3 ) ) , 2 ) , ( ( 5 , ( 5 , 2 ) $$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$ $$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

Cakupan pengaturan daya

Tujuan dari bagian ini adalah untuk memeriksa apakah set minimal yang ditemukan mampu menutup set jumlah daya. Ada kemungkinan bahwa solusi yang ditemukan dapat mencakup semua jumlah yang diberikan, tetapi mereka bukan jumlah set daya. (Secara teknis, Anda bisa membuat set jumlah daya dari set minimal yang ditemukan dan memeriksa apakah setiap jumlah, seperti set daya yang ditentukan, ada dalam set jumlah awal. Ini semua yang baru saja digabungkan dengan apa yang sudah kita miliki, jadi tidak ada yang terbuang. Anda dapat melakukan bagian ini sambil memutar kembali rekursi.)

1. Mengkodekan semua elemen dari set minimal menggunakan kekuatan berurutan 2. Urutan tidak penting. Encode elemen yang sama dengan nilai baru sebanyak yang diulang. Mulai dari C = 1, setiap elemen berikutnya memiliki C = 2C.

$$(2=[1],3=[2],5=[4],5=[8])$$

2. Ganti elemen dalam daftar rekursi yang dipulihkan,

$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

dengan pengkodean: 2 dengan 1, 3 dengan 2, 5 dengan 4, dan 5 lainnya dengan 8. Perhatikan bahwa setiap elemen memiliki pengkodean yang berbeda meskipun mereka diulang.

$$((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))$$

3. Kumpulkan semua jumlah menengah, saat ini kami memiliki (1,2,4,8)

$$((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))$$

Jumlah menengah$(1,2,3,4,5,8,9,10)$

$$((14),1),((13),2),((7),8),(15)$$

Jumlah menengah$(1,2,3,4,5,8,9,10,13,14,15)$

$$\{(15),(15),(15),(15)\}$$

4. Periksa bahwa hasilnya , di mana adalah jumlah elemen dalam solusi, dalam contoh$2^m-1$$m$$m=4$

5. Kumpulkan angka yang hilang dari hingga dalam daftar jumlah menengah$1$$2^m-1$

$(6,7,11,12)$

6. Membenarkan ketidakhadiran mereka dengan cara berikut: mewakili setiap angka dalam bentuk biner

$(6=0110_2)$ $(7=0111_2)$ $(11=1011_2)$ $(12=1010_2)$

$6$ menunjukkan jumlah 3 + 5 karena mencakup elemen kedua dan ketiga dari . Jumlah elemen-elemen ini, 8, tercantum dalam daftar jumlah awal , jadi semuanya baik-baik saja.$0110_2$$(2=[1],3=[2],5=[4],5=[8])$$\{2,3,5,7,8,10,12,13,15\}$

$7$ mewakili jumlah 2 + 3 + 5 karena mencakup tiga elemen pertama dari . Jumlah elemen-elemen ini, 10, terdaftar dalam daftar jumlah awal sehingga semuanya baik-baik saja.$0111_2$$(2=[1],3=[2],5=[4],5=[8])$

$11$ adalah 2 + 3 + 5, dan 10 ada dalam daftar. adalah 3 + 5, dan 8 ada dalam daftar.$12$

Jika representasi biner sesuai dengan jumlah yang tidak dapat ditemukan, laporkan bahwa tidak ada solusi.

Jadi semuanya baik-baik saja dan adalah solusinya. Ini adalah solusi minimal juga.$(2,3,5,5)$

Diskusi

Itu perlu untuk menyediakan algoritma yang akan memeriksa apakah jumlahnya mencakup penyelesaian set daya, yang tersembunyi dalam ekspansi biner. Sebagai contoh jika kita mengecualikan 8 dan 7 dari contoh awal, bagian pertama masih akan memberikan solusi, hanya bagian kedua akan melaporkan kombinasi jumlah yang hilang.

Bagian pertama dari menemukan kemungkinan set minimal yang datang ke : kami sedang mencari di sekitar elemen kali memiliki satu pencarian biner.$mnlog(m)$$m\log^2(m)$$m$$n$$\log(m)$

Bagian terakhir dilakukan dalam pengembalian rekursi dan tidak memerlukan upaya khusus, kami mencari kurang dari elemen, kami membutuhkan bentuk biner yang dan kami memiliki satu tambahan dan mencari jika jumlahnya ada di daftar, jadi bersama-sama ini lagi tentang .$m$$\log{m}$$m\log^2(m)$

Jika kita mengasumsikan bahwa jumlah elemen dalam himpunan jumlah daya sesuai dengan jumlah partisi elemen terbesar dalam himpunan yang mendasari maka kompleksitasnya adalah sekitar . Salah satu dari keduanya membenarkan penyortiran awal untuk menemukan elemen terbesar.$m\log^3(m)$

Bagian dari algoritma mengasumsikan bahwa kita dapat menemukan pasangan jumlah dalam waktu linier dan ini membutuhkan penyortiran.

Mulai salah

Bagian pertama dari algoritma mungkin gagal, jika kita memulainya dengan cara yang salah. Misalnya memiliki solusi dasar yang Anda dapatkan jika Anda memulai algoritma dari 6. Namun kami dapat memulai algoritme kami dari 7, karena tidak ada dalam langkah 4. yang mengatakan tidak, dan mengunci diri, algoritme tidak dapat berakhir dengan baik. Alasannya adalah bahwa 7 adalah 7 = 4 + 3 dan 4 dan 3 ada dalam solusi. Jadi algoritma terkunci tidak selalu berarti bahwa tidak ada solusi, hanya untuk mencoba lagi dengan nilai awal yang lebih rendah. Dalam hal ini, beberapa ide tentang nilai yang mungkin disembunyikan di dalam tersisa . Itu sebabnya kami menyarankan mulai dari sana jika terjadi kegagalan.$2,3,4,5,6,7,8,9,10,11,12,13,15$$2,3,4,6$$S_{ij}$

Contoh lain, jika Anda kehilangan dan memulai algoritma dari 5, Anda akan mendapatkan tetapi yang ini tidak termasuk 2.$5,4,3,3$

Perhatikan bahwa algoritma ini tidak akan memberikan solusi turunan seperti , yang kami dapatkan hanya dengan mengubah 6 menjadi 4 dan 2 dalam solusi . Ada aturan khusus yang mencakup versi ini.$2,2,3,4,4$$2,3,4,6$

Tujuan dari algoritma ini adalah untuk memberikan solusi setelah kami memulai semuanya dengan benar.

Perbaikan

Langkah 4. adalah yang bisa ditingkatkan dengan cara ini: alih-alih maksimal kita bisa mencoba setiap elemen dalam urutan menurun yang memenuhi kondisi yang diberikan. Kami membuat cabang terpisah untuk masing-masing. Jika beberapa cabang tidak memberikan solusi, batalkan.

Misalnya untuk kita bisa mencoba di babak pertama secara terpisah karena semuanya lulus tes pertama. (Tidak ada alasan untuk menggunakan 2 atau 3 karena kita tahu mereka harus berada di set yang mendasarinya.) Dan hanya melanjutkan seperti itu di sekitar sampai kita mengumpulkan semua versi yang dapat mencapai akhir. Ini akan menciptakan solusi cakupan penuh yang akan menemukan lebih dari satu set yang mendasarinya.$2,3,4,5,6,7,8,9,10,11,12,13,15$$7,6,5,4$

Hal lain, karena kita tahu bahwa kita tidak dapat memiliki lebih dari satu pengulangan jika kasusnya minimal, kita dapat memasukkan ini ke dalam algoritma kita.

Secara keseluruhan, kondisi pada langkah 4. bahwa angka harus diulang dalam setiap kelompok atau memiliki kemampuan untuk membuat jumlah cukup kuat untuk mengeluarkan kita dari perairan eksponensial langsung, yang akan menjadi algoritma dengan hanya mencoba setiap kombinasi dan menciptakan kekuatan atur masing-masing sampai kami menemukan kecocokan.

CATATAN: Ini tidak berfungsi secara umum, lihat contoh berlawanan Uri di bawah ini.

Salah satu cara untuk mencapai setidaknya 1. dan 2. untuk himpunan (minimal memerlukan sedikit penyesuaian) adalah (menyortir terlebih dahulu, jika perlu):$Y$$Y$

• Periksa apakah . Jika tidak, tidak ada solusi.$0\in Y$
• Biarkan menjadi angka positif terkecil di . Maka juga harus dalam , jika ada (kalau tidak itu akan menjadi jumlah dari angka positif yang lebih kecil, yang juga akan terjadi di ).$y$$Y$$y$$X$$Y$
• Biarkan menjadi anggota tersisa . Kami akan mencoba menemukan himpunan sehingga . Jelas harus dalam . Untuk : jika , tambahkan ke ; jika tidak, jika , tidak ada solusi; jika tidak (yaitu jika , tetapi ), kita tidak perlu di .$z_1<\dots<z_n$$Y$$Y'$$Y = Y' + \{0,y\}$$0$$Y'$$i=1,\dots,n$$z_i+y\in Y$$z_i$$Y'$$z_i-y\notin Y$$z_i+y\notin Y$$z_i+y\in Y$$z_i$$Y'$
• Ulangi secara rekursif dengan , mengumpulkan elemen minimal menjadi multiset. Ini adalah solusi Anda jika Anda berakhir dengan set kosong.}$Y'$$y,y',\dots$

Dalam setiap langkah rekursif, ukuran set berkurang setidaknya (karena kita mengecualikan elemen terkecil ), sehingga jumlah langkah dalam . Setiap langkah berisi satu iterasi atas set saat ini, untuk kompleksitas total (dengan asumsi biaya unit untuk operasi aritmatika).$1$$y$$O(n)$$O(n^2)$

Menemukan solusi minimal (perhatikan bahwa ini tidak selalu unik; misalnya, untuk kami memiliki dan ) sedikit lebih terlibat: setelah menemukan minimum , Anda akan menganalisis perkembangan aritmatika di , tolak jika salah satu dari mereka adalah singleton, dan jika tidak memilih anggota berganti untuk ; jika suatu perkembangan memiliki panjang yang ganjil, Anda perlu memilih beberapa anggota yang berurutan, karena itu keunikannya.$Y=\{0,1,3,4,5,6,7\}$$\{0,1,3,4,6\}$$\{0,1,3,5,6\}$$y\in Y$$\{a+k\cdot y\}$$Y$$Y'$