Partition Equal Subset Sum

Q: Mengapa Partition Equal Subset Sum merupakan masalah knapsack 0/1?

Kamu mengisi ransel berukuran target = total / 2 secara tepat, dengan menggunakan setiap nilai paling banyak satu kali. Mengambil atau meninggalkan nilai adalah pilihan 0/1, dan ukuran suatu nilai adalah nilai itu sendiri. Tabel jumlah yang dapat dicapai menjawabnya dalam waktu O(n × target).

Q: Berapa kompleksitas waktu untuk membagi himpunan menjadi dua bagian dengan jumlah yang sama?

Waktu O(n × target), dengan target adalah setengah dari total, dan memori O(target) dengan satu baris: sekitar 2 × 10^6 langkah untuk 200 nilai yang masing-masing paling banyak 100. Batas ini bertambah seiring ukuran nilai, jadi bersifat pseudo-polinomial; masalah umumnya adalah NP-complete.

SedangDynamic programming

+10

Kamu mendapatkan array nums berisi bilangan bulat positif. Tentukan apakah kamu bisa membagi nilai-nilai tersebut menjadi dua kelompok dengan jumlah yang sama. Setiap nilai harus masuk tepat ke satu kelompok, dan kelompok bisa mengambil nilai dari posisi mana pun. Kembalikan true jika pembagian seperti itu bisa dilakukan, dan false jika tidak.

Fungsi

canPartition(nums: integer-array) → boolean

numsinteger-array: nilai positif yang akan dibagi menjadi dua kelompok
Mengembalikanboolean: true jika nilai-nilai dapat membentuk dua kelompok dengan jumlah yang sama, false jika tidak

Batasan

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100

Contoh

Input: nums = [6, 1, 4, 9, 2]
Output: true
Penjelasan: Jumlahnya 22, jadi setiap kelompok membutuhkan 11. Kelompok 9 + 2 dan 6 + 1 + 4 sama-sama berjumlah 11, jadi jawabannya true.

Input: nums = [4, 7, 2, 9, 6]
Output: false
Penjelasan: Jumlahnya 28, jadi setiap kelompok membutuhkan 14. Kelompok yang berisi 9 membutuhkan 5 lagi, dan tidak ada kombinasi 4, 7, 2, dan 6 yang menghasilkan 5, jadi jawabannya false meskipun jumlahnya genap.

Input: nums = [1, 2, 3, 5]
Output: false
Penjelasan: Jumlahnya adalah 11. Dua bilangan bulat yang sama selalu menghasilkan jumlah genap, jadi jumlah ganjil tidak mungkin dibagi menjadi dua bagian yang sama dan jawabannya adalah false.

Pertanyaan lanjutan

Jika tidak ada pembagian yang sama rata, bisakah kamu mengembalikan selisih sekecil mungkin antara jumlah kedua kelompok?

Petunjuk

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

0 dari 3 dibuka

Solusi

Setiap kelompok harus memiliki setengah dari total, jadi pertanyaannya menjadi: apakah ada subset dari nums yang jumlahnya sama dengan target = total / 2? Mencoba setiap subset membutuhkan 2^n langkah. Namun, jumlahnya kecil, paling banyak 200 × 100 / 2 = 10^4, jadi tabel knapsack 0/1 yang mencatat jumlah yang dapat dicapai bisa menjawabnya dalam O(n × target) langkah.

Coba setiap subset dengan rekursi

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Jika totalnya ganjil, pembagian tidak mungkin dilakukan. Jika tidak, pilih nilai untuk grup pertama hingga jumlahnya mencapai target; nilai yang tersisa dengan sendirinya membentuk bagian lainnya. Fungsi pembantu reach(i, remaining) menentukan setiap nilai secara bergiliran: ambil nums[i] atau lewati.

Setiap subset adalah satu jalur pilihan, jadi pencarian tidak mungkin melewatkan suatu pembagian. Input tanpa pembagian akan memaksanya menjelajahi hampir semua jalur, hingga 2^n: sekitar 10^12 untuk n = 40 dan 1.6 × 10^60 untuk n = 200.

Algoritma

Jumlahkan nums. Jika totalnya ganjil, kembalikan false.
Tetapkan target menjadi setengah dari total.
Tulis reach(i, remaining): kembalikan true saat remaining bernilai 0, dan false saat i melewati nilai terakhir atau remaining kurang dari 0.
Jika tidak, kembalikan reach(i+1, remaining-nums[i]) atau reach(i+1, remaining): ambil nilainya atau biarkan.
Kembalikan reach(0, target).

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False

    # Can some of the values from index i on add up to exactly remaining?
    def reach(i, remaining):
        if remaining == 0:
            return True
        if i == len(nums) or remaining < 0:
            return False
        # Put nums[i] in the first group, or leave it for the second one
        return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)

    return reach(0, total // 2)

Isi tabel berdasarkan nilai dan jumlah

Intuisi

reach(i, remaining) hanya bergantung pada dua angka, jadi jumlah pertanyaan yang berbeda paling banyak (n+1) × (target+1), sekitar 201 × 10001 ≈ 2 × 10^6. Jawab masing-masing satu kali dalam tabel: can[i][s] menunjukkan apakah beberapa nilai pertama berjumlah s. Baris 0 bernilai false, kecuali can[0][0].

Nilai num = nums[i-1] bisa tidak dipilih, sehingga nilai-nilai sebelumnya sudah mencapai s, atau dipilih, sehingga nilai-nilai tersebut mencapai s-num. Setiap baris hanya membaca baris di atasnya, jadi setiap nilai digunakan paling banyak satu kali. Dalam contoh pertama, jumlah yang dapat dicapai bertambah dari {0} menjadi {0, 6}, {0, 1, 6, 7}, lalu {0, 1, 4, 5, 6, 7, 10, 11}: 6 + 1 + 4 menghasilkan 11.

Algoritma

Kembalikan false untuk total ganjil dan tetapkan target menjadi setengah dari total tersebut.
Buat tabel dengan n+1 baris dan target+1 kolom, semuanya bernilai false, lalu tetapkan can[0][0] menjadi true.
Untuk setiap baris i dari 1 hingga n, ambil num = nums[i-1].
Untuk setiap jumlah s dari 0 hingga target, tetapkan can[i][s] menjadi can[i-1][s] atau, jika s ≥ num, can[i-1][s-num].
Kembalikan can[n][target].

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2
    n = len(nums)

    # can[i][s] is True when some of the first i values add up to s
    can = [[False] * (target + 1) for _ in range(n + 1)]
    can[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 and reach s - num with the values before it
            can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
    return can[n][target]

Satu baris penjumlahan, diisi dari atas ke bawah

Intuisi

Setiap baris hanya membaca baris di atasnya, jadi pertahankan satu reach dan perbarui nilainya langsung. Urutan pembaruan itu penting. Jika kamu menelusuri s ke atas, kamu membaca jumlah yang sudah dinyalakan oleh nilai yang sama ini: pada contoh pertama, angka 1 akan menandai jumlah 1, lalu membacanya untuk menandai 2, kemudian 3, seolah-olah kamu memiliki banyak angka 1.

Telusuri s ke bawah, mulai dari target hingga num. Dengan begitu, s-num adalah indeks yang belum disentuh oleh nilai ini, jadi reach[s-num] masih sama dengan can[i-1][s-num]. Kamu bisa berhenti setelah reach[target] bernilai true, karena nilai-nilai berikutnya tidak pernah menghapus jumlah. Waktunya tetap O(n × target), dan memorinya berkurang menjadi target + 1 boolean.

Algoritma

Kembalikan false untuk total ganjil dan tetapkan target ke setengah dari total tersebut.
Buat reach dengan target + 1 entri, semuanya bernilai false kecuali reach[0].
Untuk setiap nilai num, telusuri s dari target turun hingga num dan tetapkan reach[s] ke true saat reach[s-num] bernilai true.
Setelah setiap nilai, kembalikan true jika reach[target] bernilai true.
Jika perulangan berakhir, kembalikan reach[target], yang bernilai false.

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2

    # reach[s] is True when some of the values seen so far add up to s
    reach = [False] * (target + 1)
    reach[0] = True
    for num in nums:
        # Walk the sums downward so num is used at most once
        for s in range(target, num - 1, -1):
            if reach[s - num]:
                reach[s] = True
        if reach[target]:
            return True
    return reach[target]

Jebakan dan kasus tepi

Menelusuri jumlah ke atas dalam versi satu baris. Dengan [3, 9] dan target 6, angka 3 menandai jumlah 3 lalu jumlah 6, dan kamu menjawab true.
Melewatkan pemeriksaan ganjil. Untuk [1, 2], total 3 dibulatkan ke bawah menjadi target 1, nilai 1 mencapainya, dan kamu menjawab true.
Menambahkan setiap nilai ke kelompok yang lebih ringan. Pada [3, 3, 2, 2, 2], hasil akhirnya 7 dibandingkan dengan 5, sementara 3 + 3 = 2 + 2 + 2.
Tidak melewatkan nilai yang lebih besar dari target, seperti pada [2, 2, 2, 10]. Di R, rentang seperti (num+1):(target+1) lalu menghitung mundur dan menghentikan perulangan.
Membaca jumlah s pada indeks s di Lua atau R, padahal letaknya di s + 1.

Pertanyaan yang sering diajukan3

Mengapa Partition Equal Subset Sum merupakan masalah knapsack 0/1?

Kamu mengisi ransel berukuran target = total / 2 secara tepat, dengan menggunakan setiap nilai paling banyak satu kali. Mengambil atau meninggalkan nilai adalah pilihan 0/1, dan ukuran suatu nilai adalah nilai itu sendiri. Tabel jumlah yang dapat dicapai menjawabnya dalam waktu O(n × target).

Berapa kompleksitas waktu untuk membagi himpunan menjadi dua bagian dengan jumlah yang sama?

Waktu O(n × target), dengan target adalah setengah dari total, dan memori O(target) dengan satu baris: sekitar 2 × 10^6 langkah untuk 200 nilai yang masing-masing paling banyak 100. Batas ini bertambah seiring ukuran nilai, jadi bersifat pseudo-polinomial; masalah umumnya adalah NP-complete.

Bisakah Partition Equal Subset Sum diselesaikan dengan bitset?

Ya. Simpan jumlah yang dapat dicapai sebagai bit dari satu angka besar, dimulai dengan bit 0 yang disetel. Untuk setiap nilai, bits |= bits << num menambahkannya ke semua jumlah yang dapat dicapai sekaligus, dan jawabannya adalah bit target. Ini adalah tabel yang sama, dengan 64 jumlah per word mesin.

def canPartition(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [6, 1, 4, 9, 2]

Output yang diharapkan

true

Partition Equal Subset Sum

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Coba setiap subset dengan rekursi

Isi tabel berdasarkan nilai dan jumlah

Satu baris penjumlahan, diisi dari atas ke bawah

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa