Mengingat bobot dan keuntungan dari N item, kita ingin memasukkan item tersebut ke dalam Knapsack yang berkapasitas C. Tujuannya adalah untuk mendapatkan keuntungan yang maksimal dari item yang ada di Knapsack. Setiap item hanya dapat dipilih satu kali, karena kami tidak memiliki jumlah item yang lebih dari satu.

Contoh:

  • Item: [A, B, C, D]
  • Bobot: [2, 3, 1, 4]
  • Keuntungan: [4, 5, 3, 7]
  • Kapasitas: 5

Mari kita coba beberapa kombinasi yang berat totalnya kurang dari kapasitasnya, 5:

  • A + B (berat total: 5) = 9 keuntungan
  • C + D (berat total : 5) = 10 keuntungan
  • B + C (berat total: 4) = 8 keuntungan

Solusi dasar

Pemrograman Dinamis Top-down dengan Memoisasi

Kita dapat menggunakan memoisasi untuk mengatasi sub-masalah yang tumpang tindih. Sekali lagi, memoisasi adalah saat kita menyimpan hasil dari semua submasalah yang telah diselesaikan sebelumnya dan mengembalikan hasilnya dari memori jika kita menemukan masalah yang telah diselesaikan.

Karena kita memiliki dua nilai yang berubah (capacity dan currentIndex) dalam fungsi rekursif knapsackRecursive(), kita dapat menggunakan array dua dimensi untuk menyimpan hasil dari semua sub-masalah yang diselesaikan. Seperti disebutkan di atas, kita perlu menyimpan hasil untuk setiap sub-array (yaitu untuk setiap kemungkinan indeks 'i') dan untuk setiap kemungkinan kapasitas 'c'.

Pemrograman Dinamis dari Bawah ke Atas

Mari kita coba mengisi array dp[][] kita dari solusi di atas, bekerja secara bottom-up. Pada dasarnya, kami ingin mencari keuntungan maksimum untuk setiap sub-array dan untuk setiap kapasitas yang mungkin.

Artinya, dp[i][c] akan mewakili keuntungan knapsack maksimum untuk kapasitas 'c' yang dihitung dari item 'i' pertama.

Partisi Jumlah Subset yang Sama — Leetcode #416

Kode Leet #416

Masalah ini mengikuti pola Knapsack 0/1. Solusi dasar brute force adalah dengan mencoba semua kombinasi mempartisi angka-angka tertentu menjadi dua himpunan untuk melihat apakah ada pasangan himpunan yang memiliki jumlah yang sama.

Asumsikan jika S mewakili jumlah total semua bilangan tertentu, maka dua himpunan bagian yang sama harus memiliki jumlah yang sama dengan S/2. Ini pada dasarnya mengubah soal kita menjadi: 'Temukan subkumpulan bilangan tertentu yang jumlah totalnya S/2'.

Pemrograman Dinamis dari Bawah ke Atas

Mari kita coba mengisi array dp[][] kita dari solusi di atas, bekerja secara bottom-up. Pada dasarnya, kita ingin mengetahui apakah kita dapat membuat semua kemungkinan penjumlahan pada setiap subset. Artinya, dp[i][s] akan menjadi 'benar' jika kita dapat menjumlahkan 's' dari angka 'i' pertama.

Jadi, untuk setiap angka pada indeks 'i' (0 ‹= i ‹ num.length) dan jumlah 's' (0 ‹= s ‹= S/2), kita mempunyai dua pilihan:

  1. Kecualikan nomor tersebut. Dalam hal ini, kita akan melihat apakah kita bisa mendapatkan 's' dari subset tidak termasuk angka ini: dp[i-1][s]
  2. Cantumkan angka jika nilainya tidak lebih dari ‘s’. Dalam hal ini, kita akan melihat apakah kita dapat menemukan subset untuk mendapatkan jumlah sisanya: dp[i-1][s-num[i]]

Jika salah satu dari dua skenario di atas benar, kita dapat menemukan subkumpulan bilangan dengan jumlah yang sama dengan 's'.

Jumlah Subset

“Diberikan himpunan bilangan positif, tentukan apakah terdapat himpunan bagian yang jumlahnya sama dengan bilangan tertentu 'S'.”

Contoh:

  • Masukan [1, 2, 3, 7]
  • S = 6
  • Keluaran — — Benar

Masalah ini mengikuti pola Knapsack 0/1 dan sangat mirip dengan Equal Subset Sum Partition. Solusi dasar brute force adalah dengan mencoba semua himpunan bagian dari bilangan tertentu untuk melihat apakah ada himpunan yang jumlahnya sama dengan 'S'.

Pemrograman Dinamis dari Bawah ke Atas

Kami akan mencoba mencari tahu apakah kami dapat membuat semua kemungkinan penjumlahan dengan setiap subset untuk mengisi array dp[TotalNumbers][S+1].

Untuk setiap kemungkinan jumlah 's' (dimana 0 ‹= s ‹= S), kita mempunyai dua pilihan:

  1. Kecualikan nomor tersebut. Dalam hal ini, kita akan melihat apakah kita bisa mendapatkan jumlah 's' dari subset tidak termasuk angka ini =› dp[index-1][s]
  2. Cantumkan angka jika nilainya tidak lebih dari ‘s’. Dalam hal ini, kita akan melihat apakah kita dapat menemukan subset untuk mendapatkan jumlah sisanya =› dp[index-1][s-num[index]]

Selisih Jumlah Subset Minimum

Diberikan suatu himpunan bilangan positif, bagilah himpunan tersebut menjadi dua himpunan bagian dengan selisih minimum antara jumlah himpunan bagian tersebut.

Solusi Dasar

Anggaplah S1 dan S2 adalah dua himpunan bagian yang diinginkan. Solusi dasar brute-force adalah dengan mencoba menambahkan setiap elemen di S1 ​​atau S2, untuk menemukan kombinasi yang memberikan selisih jumlah minimum antara kedua himpunan.

Pemrograman Dinamis Top-down dengan Hafalan

Kami akan menggunakan array dua dimensi untuk menyimpan hasil submasalah yang diselesaikan. Kami dapat secara unik mengidentifikasi sub-masalah dari 'Indeks Saat Ini' dan 'Jumlah1'; karena 'Jumlah2' akan selalu menjadi jumlah dari angka-angka yang tersisa.

Dari bawah ke atas

Anggaplah 'S' mewakili jumlah total semua angka. Jadi yang ingin kita capai dalam soal ini adalah mencari subset yang jumlahnya sedekat mungkin dengan 'S/2', karena jika kita dapat mempartisi himpunan tersebut menjadi dua himpunan bagian dengan jumlah yang sama, kita mendapatkan selisih minimumnya. yaitu nol. Ini mengubah soal kita menjadi Jumlah Subset, di mana kita mencoba mencari subset yang jumlahnya sama dengan bilangan tertentu — 'S/2' dalam kasus kita. Jika kita tidak dapat menemukan himpunan bagian tersebut, maka kita ambil himpunan bagian yang mempunyai jumlah paling mendekati ‘S/2’. Hal ini dapat dilakukan dengan mudah, karena kita akan menghitung semua kemungkinan jumlah pada setiap subset.

Intinya, kita perlu menghitung semua kemungkinan penjumlahan hingga 'S/2' untuk semua angka. Jadi bagaimana kita mengisi array db[TotalNumbers][S/2+1] secara bottom-up?

Untuk setiap kemungkinan jumlah 's' (dimana 0 ‹= s ‹= S/2), kita mempunyai dua pilihan:

  1. Kecualikan nomor tersebut. Dalam hal ini, kita akan melihat apakah kita bisa mendapatkan jumlah 's' dari subset tidak termasuk angka ini =› dp[index-1][s]
  2. Cantumkan angka jika nilainya tidak lebih dari ‘s’. Dalam hal ini, kita akan melihat apakah kita dapat menemukan subset untuk mendapatkan jumlah sisanya =› dp[index-1][s-num[index]]

Jika salah satu dari dua skenario di atas benar, kita dapat menemukan subset dengan jumlah yang sama dengan ‘s’. Kita harus menggali lebih dalam sebelum kita dapat mempelajari cara menemukan subset terdekat.

Hitungan Jumlah Subset

Diberikan sekumpulan bilangan positif, tentukan jumlah total himpunan bagian yang jumlahnya sama dengan bilangan 'S' tertentu.

Perintahkan ke bawah

Dari bawah ke atas

Kami akan mencoba mencari apakah kami dapat membuat semua kemungkinan penjumlahan dengan setiap subset untuk mengisi array db[TotalNumbers][S+1].

Jadi, pada setiap langkah kita mempunyai dua pilihan:

  1. Kecualikan nomor tersebut. Hitung semua himpunan bagian tanpa bilangan tertentu hingga jumlah tertentu =› dp[index-1][sum]
  2. Cantumkan angkanya jika nilainya tidak lebih dari ‘jumlah’. Dalam hal ini, kita akan menghitung semua himpunan bagian untuk mendapatkan jumlah sisanya =› dp[index-1][sum-num[index]]

Untuk mencari total himpunan, kita akan menjumlahkan kedua nilai di atas:

dp[index][sum] = dp[index-1][sum] + dp[index-1][sum-num[index]])

Jumlah Sasaran

Kode Leet #494

Diberikan sekumpulan bilangan positif (bukan nol) dan jumlah target 'S'. Setiap nomor harus diberi tanda '+' atau '-'. Kita perlu menemukan cara total untuk menetapkan simbol agar jumlah angka sama dengan target 'S'.

Kita diminta untuk menemukan dua himpunan bagian dari bilangan tertentu yang selisihnya sama dengan target 'S' yang diberikan. Katakanlah 'Jumlah(s1)' menunjukkan jumlah total himpunan 's1', dan 'Jumlah(s2)' menunjukkan jumlah total himpunan 's2'. Jadi persamaan yang diperlukan adalah:

Sum(s1) - Sum(s2) = S

Persamaan ini dapat direduksi menjadi masalah jumlah subset. Mari kita asumsikan bahwa 'Jumlah(angka)' menunjukkan jumlah total semua angka, oleh karena itu:

Sum(s1) + Sum(s2) = Sum(num)

Mari tambahkan dua persamaan di atas:

=> Sum(s1) - Sum(s2) + Sum(s1) + Sum(s2) = S + Sum(num)
    => 2 * Sum(s1) =  S + Sum(num)
    => Sum(s1) = (S + Sum(num)) / 2

Ini pada dasarnya mengubah soal kita menjadi: “Temukan jumlah himpunan bagian dari bilangan-bilangan tertentu yang jumlahnya sama dengan”,

=> (S + Sum(num)) / 2