Subset Sum Problem

Q: Bagaimana Subset Sum berkaitan dengan Partition Equal Subset Sum dan masalah knapsack 0/1?

Partition Equal Subset Sum adalah Subset Sum dengan target = total / 2 , setelah memeriksa bahwa totalnya genap. Subset Sum adalah knapsack 0/1, dengan setiap nilai menjadi bobotnya sendiri dan tas harus terisi tepat, sehingga tabel menyimpan nilai boolean, bukan nilai terbaik.

Q: Bagaimana cara menemukan nilai yang menghasilkan target?

Pertahankan seluruh tabel dan mulai dari made[n][target] . Naik satu baris setiap kali: jika made[i-1][s] bernilai true, nums[i-1] tidak diperlukan; jika tidak, catat dan kurangi nilainya dari s . Berhentilah saat jumlahnya 0 dengan satu pilihan yang valid.

SedangDynamic programming

+10

nums berisi bilangan bulat positif, dan target adalah bilangan bulat positif. Bisakah kamu memilih beberapa nilai, setiap posisi paling banyak satu kali, sehingga jumlahnya tepat sama dengan target? Kembalikan true jika bisa, dan false jika tidak ada pilihan yang berhasil.

Fungsi

isSubsetSum(nums: integer-array, target: integer) → boolean

numsinteger-array: nilai positif yang dapat kamu pilih
targetinteger: jumlah tepat yang harus dicapai oleh nilai yang dipilih
Mengembalikanboolean: benar jika beberapa nilai jika dijumlahkan menghasilkan tepat target, salah jika tidak

Batasan

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 10⁴
1 ≤ target ≤ 10⁴

Contoh

Input: nums = [8, 3, 11, 5, 7]target = 15
Output: true
Penjelasan: 8 + 7 = 15, jadi jawabannya adalah true. Pilihan 3 + 5 + 7 juga berhasil, satu pilihan saja sudah cukup.

Input: nums = [6, 9, 12, 15]target = 20
Output: false
Penjelasan: Setiap nilai merupakan kelipatan 3, jadi setiap jumlahnya juga merupakan kelipatan 3. 20 bukan kelipatan 3, jadi jawabannya adalah false.

Input: nums = [4, 1, 2]target = 8
Output: false
Penjelasan: Ketiga nilai jika dijumlahkan menjadi 4 + 1 + 2 = 7, yang kurang dari 8, jadi tidak ada pilihan yang dapat mencapainya dan jawabannya adalah false.

Pertanyaan lanjutan

Dua nilai yang sama di posisi berbeda dihitung sebagai pilihan yang berbeda. Berapa banyak pilihan yang menghasilkan target?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap nilai memiliki pilihan ya atau tidak, jadi 200 nilai menghasilkan 2^200 pilihan. Namun, yang penting hanya jumlah hingga target ≤ 10^4. Catat jumlah yang bisa dibentuk oleh nilai-nilai sejauh ini: setiap nilai baru menggeser catatan itu sebesar nilainya, dan pencarian berubah menjadi tabel boolean berukuran n × target.

Ambil atau lewati setiap nilai

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

canMake(i, remaining) menanyakan apakah nilai mulai dari posisi i dapat menghasilkan tepat remaining. Ambil nums[i] jika nilainya sesuai, sehingga tersisa remaining-nums[i] untuk sisanya. Jika gagal, lewati nilai itu. Setiap pilihan adalah satu jalur, jadi pencarian akan menemukan pilihan jika ada.

Jika tidak ada pilihan, pencarian akan memeriksa semuanya. Dengan 200 kelipatan 3, masing-masing paling besar 300, dan target 9998, tidak ada pilihan yang berhasil, tetapi kombinasi 33 nilai apa pun tetap di bawah target: lebih dari 10^37 jalur.

Algoritma

Tulis canMake(i, remaining).
Nilai remaining sebesar 0 berarti pemilihan selesai: kembalikan true. Jika tidak ada nilai tersisa dan masih ada yang harus dibuat, kembalikan false.
Jika nums[i] ≤ remaining dan canMake(i+1, remaining-nums[i]) bernilai true, kembalikan true.
Jika tidak, kembalikan canMake(i+1, remaining).
Kembalikan canMake(0, target).

def isSubsetSum(nums, target):
    n = len(nums)

    # Can some of nums[i], nums[i+1], ... add up to exactly remaining?
    def can_make(i, remaining):
        if remaining == 0:
            return True
        if i == n:
            return False
        if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
            return True  # take nums[i]
        return can_make(i + 1, remaining)  # skip it

    return can_make(0, target)

Isi tabel jumlah yang dapat dicapai

Intuisi

Rekursi hanya bergantung pada posisi dan jumlah tersisa antara 0 dan target, dan banyak jalur mencapai pasangan yang sama. Isi tabel sebagai gantinya. made[i][s] bernilai true ketika pilihan dari i nilai pertama menghasilkan jumlah tepat s; pilihan kosong menghasilkan 0. Dengan num = nums[i-1], jumlah s dapat dibuat jika jumlah itu dapat dibuat tanpa num, yaitu made[i-1][s], atau jika num melengkapi s-num, yaitu made[i-1][s-num] dengan s ≥ num.

Pada contoh pertama, setelah angka 8, jumlah yang dapat dibuat adalah 0 dan 8. Angka 3 menambahkan 3 dan 11, angka 11 hanya menambahkan 14, angka 5 menambahkan 5 dan 13, dan 8 + 7 mencapai 15. Pada batas maksimum, tabel memiliki 201 × 10001 sel, sekitar 2 × 10^6 langkah.

Algoritma

Alokasikan made sebagai n+1 baris dengan masing-masing target+1 nilai boolean, semuanya false. Tandai made[0][0] sebagai true untuk pilihan kosong.
Baris i menangani nilai num = nums[i-1], untuk i = 1 hingga n.
Untuk setiap jumlah s dari 0 hingga target, tetapkan made[i][s] menjadi made[i-1][s].
Jika s ≥ num dan made[i-1][s-num] bernilai true, tetapkan made[i][s] menjadi true.
Kembalikan made[n][target].

def isSubsetSum(nums, target):
    n = len(nums)
    # made[i][s]: some of the first i values add up to exactly s
    made = [[False] * (target + 1) for _ in range(n + 1)]
    made[0][0] = True
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            # leave num out, or put it in on top of a sum of s-num
            made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
    return made[n][target]

Satu baris penjumlahan, diperbarui dari atas

Intuisi

Setiap baris hanya membaca baris sebelumnya, jadi satu array made[s] dapat menyimpannya. Jika kamu menimpanya ke atas, sebuah nilai akan menggunakan nilainya sendiri: dengan nums = [5] dan target 10, s = 5 menjadi true, lalu s = 10 membaca entri baru itu, sehingga angka 5 digunakan dua kali.

Telusuri dari target turun ke num. Pembacaan pada s-num mengakses sel yang lebih rendah dan belum ditulis ulang selama penelusuran, sehingga baris yang terbaca adalah baris sebelum num. Jumlah yang sudah tercapai akan tetap tercapai, jadi kamu dapat berhenti begitu made[target] bernilai true. Penggunaan memori turun menjadi target + 1 nilai boolean.

Algoritma

Mulai dengan satu array boolean berukuran target + 1, dengan hanya made[0] yang bernilai true.
Ambil nilai secara berurutan. Untuk setiap num, jalankan s secara menurun dari target hingga num.
Setiap kali made[s-num] bernilai true, tandai made[s].
Berhenti dengan hasil true begitu made[target] ditandai.
Jika semua nilai habis digunakan lebih dahulu, jawabannya adalah false.

def isSubsetSum(nums, target):
    # made[s]: some of the values seen so far add up to exactly s
    made = [False] * (target + 1)
    made[0] = True
    for num in nums:
        # Downward, so made[s - num] still ignores num
        for s in range(target, num - 1, -1):
            if made[s - num]:
                made[s] = True
        if made[target]:
            return True
    return False

Jebakan dan kasus tepi

Perulangan yang naik pada jumlah menggunakan nilai dua kali: [3] dengan target 9 menghasilkan jawaban true.
Lupa menetapkan made[0] = true. Setiap jumlah dibangun dari pilihan kosong, jadi semua jawaban menjadi false.
Memilih nilai terbesar terlebih dahulu. Pada [6, 5, 5] dengan target 10, mengambil 6 menyisakan 4, yang tidak bisa dibentuk, sedangkan 5 + 5 = 10.
Nilai yang lebih besar dari target, seperti pada [10000] dengan target 1, tidak boleh mengubah apa pun. num...target di Swift menghentikan program dan (num+1):(target+1) di R menghitung mundur, jadi periksa num ≤ target terlebih dahulu.
Di Lua dan R, entri untuk jumlah s berada pada indeks s + 1.

Pertanyaan yang sering diajukan4

Berapa kompleksitas waktu dari masalah subset sum?

Tabel ini membutuhkan waktu O(n × target), sekitar 2 × 10^6 langkah untuk 200 nilai dan target 10^4, sementara satu baris mengurangi penggunaan memori menjadi O(target). Biayanya mengikuti ukuran numerik target, sehingga method ini bersifat pseudopolinomial dan tidak berguna untuk target seperti 10^18. Secara umum, subset sum adalah NP-complete.

Bagaimana Subset Sum berkaitan dengan Partition Equal Subset Sum dan masalah knapsack 0/1?

Partition Equal Subset Sum adalah Subset Sum dengan target = total / 2, setelah memeriksa bahwa totalnya genap. Subset Sum adalah knapsack 0/1, dengan setiap nilai menjadi bobotnya sendiri dan tas harus terisi tepat, sehingga tabel menyimpan nilai boolean, bukan nilai terbaik.

Apakah subset sum berfungsi dengan angka negatif?

Idenya berhasil, tetapi kode di atas tidak. Jika ada bilangan negatif, jumlah yang dapat dicapai berkisar dari total bilangan negatif hingga total bilangan positif. Jadi, geser setiap indeks sebesar jumlah terendah itu dan isi baris dengan cara yang sama. Nilai yang lebih besar daripada sisa jumlah tidak lagi bisa dilewati.

Bagaimana cara menemukan nilai yang menghasilkan target?

Pertahankan seluruh tabel dan mulai dari made[n][target]. Naik satu baris setiap kali: jika made[i-1][s] bernilai true, nums[i-1] tidak diperlukan; jika tidak, catat dan kurangi nilainya dari s. Berhentilah saat jumlahnya 0 dengan satu pilihan yang valid.

def isSubsetSum(nums, target):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [8, 3, 11, 5, 7]
target = 15

Output yang diharapkan

true

Subset Sum Problem

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Ambil atau lewati setiap nilai

Isi tabel jumlah yang dapat dicapai

Satu baris penjumlahan, diperbarui dari atas

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan4

Soal serupa