Knapsack 0/1: Ambil atau Tinggalkan
Memaksimalkan nilai dalam batas bobot
Knapsack 0/1: Ambil atau Tinggalkan adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Kisah Ransel
Anda memiliki tas dengan batas bobot dan setumpuk barang. Ransel 0/1 menanyakan: barang mana yang memaksimalkan nilai tanpa membuat tas kelebihan muatan? 🎒
Ambil atau Lewati
Istilah 0/1 berarti setiap barang diambil sepenuhnya atau dilewati sepenuhnya. Anda tidak pernah dapat mengambil separuh barang, jadi setiap pilihan hanya ya atau tidak.
Mengapa Strategi Serakah Gagal
Mengambil barang termurah atau paling bernilai terlebih dahulu dapat membuang kapasitas. Jalan pintas serakah gagal di sini, jadi Anda perlu mempertimbangkan kombinasi yang sebenarnya.
Dua Masukan
Anda diberikan dua daftar paralel: bobot dan nilai untuk setiap barang, serta satu kapasitas. Barang i memiliki bobot wt[i] dan nilai val[i].
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7Tentukan Keadaannya
Misalkan dp[i][w] adalah nilai terbaik dengan menggunakan i barang pertama dan kapasitas w. Menamai keadaan secara tepat adalah inti persoalannya.
Pilihan untuk Melewati
Jika Anda melewati barang i, nilainya tetap seperti yang sudah Anda miliki: dp[i-1][w]. Kapasitas tetap utuh untuk barang-barang berikutnya.
Pilihan untuk Mengambil
Jika Anda mengambil barang i, tambahkan nilainya dan kurangi kapasitas: val[i] + dp[i-1][w - wt[i]]. Ini hanya boleh dilakukan jika w setidaknya sebesar wt[i].
Pilih Cabang yang Lebih Baik
Rekurensinya cukup mempertahankan pilihan yang lebih besar dari kedua opsi dengan max. Setiap sel mengandalkan jawaban yang sudah dihitung sebelumnya.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])Baris Dasar
Dengan nol barang, Anda dapat membawa nilai nol pada kapasitas berapa pun. Kasus dasar tersebut mengisi baris pertama dengan angka nol sebagai dasar perhitungan.
dp = [[0] * (cap + 1) for _ in range(n + 1)]Isi Tabelnya
Lakukan perulangan barang pada lintasan luar dan kapasitas pada lintasan dalam. Setiap sel hanya membaca baris di atasnya, sehingga satu sapuan mengisi semuanya.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]Baca Jawabannya
Sel kanan bawah dp[n][cap] menyimpan nilai maksimum untuk semua barang dan kapasitas penuh. Sel tunggal tersebut adalah jawaban akhir Anda.
Pemeriksaan Cepat
Uji rekurensi inti ransel 0/1.
Rangkuman
Anda telah mempelajari ransel 0/1: setiap barang diambil atau dilewati, dp[i][w] menyimpan pilihan terbaik antara melewati dan mengambil, dan dp[n][cap] adalah jawabannya. 🎉
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Knapsack 0/1: Ambil atau Tinggalkan” gratis?
Ya — teks lengkap “Knapsack 0/1: Ambil atau Tinggalkan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Knapsack 0/1: Ambil atau Tinggalkan”?
Memaksimalkan nilai dalam batas bobot Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Knapsack 0/1: Ambil atau Tinggalkan” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Knapsack 0/1: Ambil atau Tinggalkan
- Knapsack dengan Optimasi Ruang
- DP Tanpa Batas & Pertukaran Koin
- Jumlah Subset & Partisi