Bagaimana Anda akan menguji semua kemungkinan kombinasi penambahan dari satu set N
angka sehingga mereka menambahkan hingga angka akhir yang diberikan?
Contoh singkat:
- Set angka untuk ditambahkan:
N = {1,5,22,15,0,...}
- Hasil yang diinginkan:
12345
Jawaban:
Masalah ini dapat diselesaikan dengan kombinasi rekursif dari semua jumlah yang mungkin menyaring orang-orang yang mencapai target. Berikut adalah algoritma dalam Python:
Jenis algoritme ini dijelaskan dengan sangat baik dalam kuliah Abstrak Pemrograman Standford berikut - video ini sangat direkomendasikan untuk memahami bagaimana rekursi bekerja untuk menghasilkan permutasi solusi.
Edit
Di atas sebagai fungsi generator, membuatnya sedikit lebih bermanfaat. Membutuhkan Python 3.3+ karena
yield from
.Berikut ini adalah versi Java dari algoritma yang sama:
Itu persis heuristik yang sama. Java saya agak berkarat tapi saya pikir mudah dimengerti.
C # konversi solusi Java: (oleh @JeremyThompson)
Solusi Ruby: (oleh @emaillenin)
Sunting: diskusi kompleksitas
Seperti orang lain menyebutkan ini adalah masalah NP-hard . Ini dapat diselesaikan dalam waktu eksponensial O (2 ^ n), misalnya untuk n = 10 akan ada 1024 kemungkinan solusi. Jika target yang Anda coba jangkau berada dalam kisaran rendah maka algoritma ini berfungsi. Jadi misalnya:
subset_sum([1,2,3,4,5,6,7,8,9,10],100000)
menghasilkan 1024 cabang karena target tidak pernah bisa menyaring solusi yang mungkin.Di sisi lain
subset_sum([1,2,3,4,5,6,7,8,9,10],10)
hanya menghasilkan 175 cabang, karena target yang akan dicapai10
dapat menyaring banyak kombinasi.Jika
N
danTarget
merupakan angka besar, seseorang harus pindah ke versi perkiraan solusi.sumber
[1, 2, 0, 6, -3, 3], 3
- ini hanya menghasilkan[1,2], [0,3], [3]
sementara kasus yang hilang seperti[6, -3, 3]
[1, 2, 5], 5
hanya keluaran[5]
, kapan[1, 1, 1, 1, 1]
,[2, 2, 1]
dan[2, 1, 1, 1]
solusi.i+1
diremaining = numbers[i+1:]
. Sepertinya algoritma itu tidak memungkinkan duplikat.[1, 1, 3]
lihat di stackoverflow.com/a/34971783/3684296 (Python)Solusi dari masalah ini telah diberikan jutaan kali di Internet. Masalahnya disebut Masalah perubahan koin . Satu dapat menemukan solusi di http://rosettacode.org/wiki/Count_the_coins dan model matematika itu di http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (atau perubahan koin Google masalah ).
Omong-omong, solusi Scala oleh Tsagadai, menarik. Contoh ini menghasilkan 1 atau 0. Sebagai efek samping, ia mencantumkan pada konsol semua solusi yang mungkin. Ini menampilkan solusi, tetapi gagal membuatnya dapat digunakan dengan cara apa pun.
Agar bermanfaat, kode harus mengembalikan a
List[List[Int]]
untuk memungkinkan mendapatkan jumlah solusi (panjang daftar daftar), solusi "terbaik" (daftar terpendek), atau semua solusi yang mungkin.Berikut ini sebuah contoh. Ini sangat tidak efisien, tetapi mudah dimengerti.
Saat dijalankan, ini akan menampilkan:
The
sumCombinations()
Fungsi dapat digunakan dengan sendirinya, dan hasilnya dapat dianalisis lebih lanjut untuk menampilkan "terbaik" solusi (daftar terpendek), atau jumlah solusi (jumlah daftar).Perhatikan bahwa meskipun seperti ini, persyaratan mungkin tidak sepenuhnya dipenuhi. Mungkin terjadi bahwa urutan setiap daftar dalam solusi menjadi signifikan. Dalam kasus seperti itu, setiap daftar harus diduplikasi sebanyak waktu karena ada kombinasi unsur-unsurnya. Atau kita mungkin hanya tertarik pada kombinasi yang berbeda.
Sebagai contoh, kami dapat mempertimbangkan bahwa
List(5, 10)
harus memberikan dua kombinasi:List(5, 10)
danList(10, 5)
. UntukList(5, 5, 5)
itu bisa memberikan tiga kombinasi atau satu saja, tergantung persyaratannya. Untuk bilangan bulat, tiga permutasi setara, tetapi jika kita berurusan dengan koin, seperti dalam "masalah perubahan koin", mereka tidak.Juga tidak disebutkan dalam persyaratan adalah pertanyaan apakah masing-masing nomor (atau koin) dapat digunakan hanya sekali atau berkali-kali. Kita dapat (dan kita harus!) Menggeneralisasikan masalah ke daftar daftar kejadian masing-masing nomor. Ini diterjemahkan dalam kehidupan nyata menjadi "apa cara yang mungkin untuk menghasilkan sejumlah uang dengan satu set koin (dan bukan satu set nilai koin)". Masalah aslinya hanyalah kasus khusus dari kasus ini, di mana kami memiliki sebanyak mungkin setiap koin yang diperlukan untuk membuat jumlah total dengan setiap nilai koin tunggal.
sumber
Dalam Haskell :
Dan J :
Seperti yang mungkin Anda perhatikan, keduanya mengambil pendekatan yang sama dan membagi masalah menjadi dua bagian: menghasilkan setiap anggota set daya, dan memeriksa jumlah masing-masing anggota untuk target.
Ada solusi lain tetapi ini yang paling mudah.
Apakah Anda memerlukan bantuan dengan salah satunya, atau menemukan pendekatan yang berbeda?
sumber
not in scope: 'subsequences'
ada petunjuk?import Data.List
Versi Javascript:
sumber
remaining = numbers.slice();
remaining.slice(i + 1);
dinyatakannumbers.slice(i + 1);
mengubah nomor array yangslice
mengembalikan salinan (dangkal), itu tidak mengubahnumbers
array.Versi C ++ dari algoritma yang sama
sumber
C # versi jawaban kode @msalvadores
sumber
Saya pikir saya akan menggunakan jawaban dari pertanyaan ini tetapi saya tidak bisa, jadi inilah jawaban saya. Itu menggunakan versi modifikasi dari jawaban dalam Struktur dan Interpretasi Program Komputer . Saya pikir ini adalah solusi rekursif yang lebih baik dan harus lebih menyenangkan para puritan.
Jawaban saya ada di Scala (dan minta maaf jika Scala saya payah, saya baru saja mulai mempelajarinya). The findSumCombinations kegilaan adalah untuk mengurutkan dan unik daftar asli untuk rekursi untuk mencegah korban penipuan.
Untuk menggunakannya:
sumber
Saya telah mengonversi logika di atas dari python ke php ..
sumber
Solusi python lainnya adalah dengan menggunakan
itertools.combinations
modul sebagai berikut:Keluaran:
[(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]
sumber
Inilah solusi di R
sumber
subset_sum(numbers = c(1:2), target = 5)
kembali"sum(1+2+2)=5"
. Tetapi kombinasi 1 + 1 + 1 + 1 + 1 tidak ada. Menetapkan target ke angka yang lebih tinggi (mis. 20) bahkan lebih banyak kombinasi yang hilang.subset_sum(1:2, 4)
harus mengembalikan tidak ada solusi karena tidak ada kombinasi 1 dan 2 yang menambah 4. Apa yang perlu ditambahkan ke fungsi saya adalah pelarian jikai
lebih besar dari panjangnyanumbers
Berikut adalah versi Java yang cocok untuk N kecil dan jumlah target yang sangat besar, ketika kompleksitas
O(t*N)
(solusi dinamis) lebih besar daripada algoritma eksponensial. Versi saya menggunakan pertemuan di serangan tengah, bersama dengan sedikit pergeseran untuk mengurangi kompleksitas dari naif klasikO(n*2^n)
keO(2^(n/2))
.Jika Anda ingin menggunakan ini untuk set dengan antara 32 dan 64 elemen, Anda harus mengubah
int
yang mewakili subset saat ini di fungsi langkah kelong
walaupun kinerja jelas akan menurun secara drastis seiring dengan meningkatnya ukuran set. Jika Anda ingin menggunakan ini untuk set dengan jumlah elemen ganjil, Anda harus menambahkan 0 ke set untuk membuatnya bernomor genap.sumber
Ini mirip dengan masalah perubahan koin
sumber
Algoritma yang sangat efisien menggunakan tabel yang saya tulis di c ++ pasangan beberapa tahun yang lalu.
Jika Anda mengatur PRINT 1, ia akan mencetak semua kombinasi (tetapi itu tidak akan menggunakan metode yang efisien).
Sangat efisien sehingga menghitung lebih dari 10 ^ 14 kombinasi dalam waktu kurang dari 10 ms.
sumber
Versi Excel VBA di bawah ini. Saya perlu menerapkan ini dalam VBA (bukan preferensi saya, jangan menilai saya!), Dan menggunakan jawaban pada halaman ini untuk pendekatan. Saya mengunggah kalau-kalau orang lain juga membutuhkan versi VBA.
Output (ditulis ke jendela Segera) harus:
sumber
Ini adalah versi yang lebih baik dengan pemformatan keluaran yang lebih baik dan fitur C ++ 11:
sumber
Versi Java non-rekursif yang terus menambahkan elemen dan mendistribusikannya di antara nilai yang mungkin.
0
Diabaikan dan berfungsi untuk daftar tetap (apa yang Anda berikan adalah apa yang dapat Anda mainkan) atau daftar angka yang berulang.Input sampel:
Output sampel:
sumber
Untuk menemukan kombinasi menggunakan excel - (cukup mudah). (Komputer Anda tidak boleh terlalu lambat)
Unduh file excel "Sum ke Target".
Ikuti petunjuk di halaman situs web.
semoga ini membantu.
sumber
Swift 3 konversi solusi Java: (oleh @JeremyThompson)
pemakaian:
sumber
Ini dapat digunakan untuk mencetak semua jawaban juga
Kompleksitas Waktu bersifat eksponensial. Urutan 2 ^ n
sumber
Saya melakukan sesuatu yang serupa untuk tugas scala. Berpikir untuk memposting solusi saya di sini:
sumber
Saya memindahkan sampel C # ke Objective-c dan tidak melihatnya dalam respons:
sumber
@ Jawaban KeithBeller dengan nama variabel yang sedikit berubah dan beberapa komentar.
sumber
Versi PHP , seperti yang terinspirasi oleh versi C # Keith Beller's.
Versi PHP bala tidak berfungsi untuk saya, karena saya tidak perlu mengelompokkan angka. Saya ingin implementasi yang lebih sederhana dengan satu nilai target, dan kumpulan angka. Fungsi ini juga akan memangkas setiap entri duplikat.
sumber
Disarankan sebagai jawaban:
Inilah solusi menggunakan generator es2015 :
Menggunakan generator sebenarnya bisa sangat berguna karena memungkinkan Anda untuk menghentikan eksekusi skrip segera setelah menemukan subset yang valid. Ini berbeda dengan solusi tanpa generator (yaitu keadaan kurang) yang harus beralih melalui setiap subset dari
numbers
sumber
Kurangi 0 di tempat pertama. Nol adalah identitas tambahan sehingga tidak berguna oleh hukum monoid dalam kasus khusus ini. Juga menyimpulkan angka negatif juga jika Anda ingin naik ke angka positif. Kalau tidak, Anda juga perlu operasi pengurangan.
Jadi ... algoritma tercepat yang dapat Anda peroleh pada pekerjaan khusus ini adalah sebagai berikut diberikan dalam JS.
Ini adalah algoritma yang sangat cepat tetapi jika Anda mengurutkan
data
array turun akan lebih cepat. Penggunaan.sort()
tidak signifikan karena algoritma akan berakhir dengan doa rekursif jauh lebih sedikit.sumber
Versi Perl (dari jawaban utama):
Hasil:
Versi Javascript:
Javascript satu-liner yang benar-benar mengembalikan hasil (alih-alih mencetaknya):
Dan favorit saya, satu-liner dengan panggilan balik:
sumber
Ini adalah Solusi Dinamis untuk JS untuk mengetahui berapa banyak cara orang bisa mendapatkan jumlah tertentu. Ini bisa menjadi solusi yang tepat jika Anda memikirkan kompleksitas waktu dan ruang.
sumber
sumber
Saya tidak menyukai Solusi Javascript yang saya lihat mengapa saya membuat satu untuk myselft menggunakan penerapan parsial, penutupan, dan rekursi:
Ok, saya terutama khawatir tentang apakah array kombinasi dapat memenuhi target kebutuhan, tetapi dengan pendekatan ini Anda dapat mulai menemukan sisa kombinasi
Di sini hanya mengatur target dan meneruskan array kombinasi.
implementasi saat ini saya datang dengan
sumber