Knapsack 0/1 dan Optimasi Ruang
Turunkan relasi rekurensi knapsack 0/1, isi tabel 2D, lalu sederhanakan menjadi array 1D dengan mengiterasi kapasitas secara terbalik
Knapsack 0/1 dan Optimasi Ruang adalah pelajaran Coding Interview Prep 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Masalah Ransel 0/1
Masalah Ransel 0/1: diberikan n barang, masing-masing memiliki bobot w[i] dan nilai v[i], serta sebuah ransel berkapasitas W. Pilih barang untuk memaksimalkan nilai total tanpa melebihi kapasitas. Setiap barang diambil tepat satu kali (0 = lewati, 1 = ambil). Ini merupakan pola dasar dari banyak masalah DP dalam wawancara, termasuk partisi himpunan bagian dengan jumlah sama dan jumlah target.
Keadaan DP dan Relasi Rekurensi
Definisikan dp[i][c] sebagai nilai maksimum dengan menggunakan i barang pertama dan kapasitas c. Ada dua pilihan untuk barang i: melewatkannya (dp[i-1][c]) atau mengambilnya jika w[i] <= c (dp[i-1][c-w[i]] + v[i]). Relasi rekurensinya adalah: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) jika w[i] <= c, sedangkan jika tidak, dp[i][c] = dp[i-1][c]. Kasus dasar: dp[0][c] = 0 untuk semua c.
Implementasi Tabel DP 2D
Tabel 2D memiliki (n+1) x (W+1) entri dan diisi baris demi baris untuk setiap barang. Setelah semua baris terisi, dp[n][W] menyimpan nilai maksimum. Algoritme ini berjalan dalam waktu O(n × W) dan ruang O(n × W) — kompleksitas pseudopolinomial yang efisien ketika W kecil.
def knapsack_2d(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c] # skip item i
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8)) # 10Mengapa Kapasitas Diiterasi Terbalik untuk DP 1D
Pengamatan utamanya: baris i hanya bergantung pada baris i-1. Jadi, kita dapat menggunakan satu larik 1D dan memperbaruinya secara langsung. Namun, jika kita mengiterasi kapasitas c dari kiri ke kanan (kecil ke besar), barang i mungkin terhitung dua kali — kita dapat menggunakan nilai yang telah diperbarui untuk c-w[i] yang sudah mencakup barang i. Iterasi dari kanan ke kiri (besar ke kecil) memastikan setiap barang digunakan paling banyak satu kali dalam setiap pembaruan baris.
# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] may already use item i
# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] still from previous rowImplementasi dengan Optimasi Ruang 1D
Dengan hanya menyimpan satu larik dan mengiterasi kapasitas dari W turun ke w[i], kita memperoleh hasil yang sama seperti tabel 2D dengan ruang O(W). Kompleksitas waktunya tetap O(n × W). Optimasi ruang ini penting untuk diingat — pewawancara sering meminta Anda mengurangi DP ransel 2D menjadi 1D.
def knapsack_1d(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(W, w - 1, -1): # iterate RIGHT TO LEFT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8)) # 10Merekonstruksi Barang yang Dipilih
Untuk mengetahui barang mana yang dipilih, Anda memerlukan tabel 2D lengkap. Setelah mengisinya, mulai dari dp[n][W] dan telusuri ke belakang: jika dp[i][c] != dp[i-1][c], berarti barang i disertakan — kurangi bobotnya dari c dan pindah ke baris i-1. Lanjutkan hingga i = 0. Optimasi 1D menghilangkan kemampuan rekonstruksi ini.
def knapsack_with_items(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c]
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
# Reconstruct
selected, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i-1][c]:
selected.append(i-1)
c -= weights[i-1]
return dp[n][W], selected[::-1]
print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))Contoh Praktis: Memaksimalkan Nilai Total
Misalkan barang-barangnya: weights=[2,3,4,5], values=[3,4,5,6], W=8. Pilihan optimal: ambil barang dengan bobot 3 (nilai 4) dan bobot 5 (nilai 6) — bobot total 8, nilai 10. Atau ambil bobot 2 dan 5 — nilai total 9. Atau bobot 2 dan 3 — nilai 7. DP menemukan nilai maksimum 10 dengan tepat. Perhatikan bahwa pendekatan rakus (mengambil rasio nilai terhadap bobot tertinggi) akan mengambil barang dengan rasio 1.5 terlebih dahulu (bobot 2, nilai 3) — tetapi itu tidak selalu optimal.
Ransel Pecahan vs Ransel 0/1
Dalam Ransel Pecahan, Anda dapat mengambil sebagian dari barang. Masalah ini dapat diselesaikan dengan pendekatan rakus dengan mengurutkan berdasarkan rasio nilai terhadap bobot. Dalam Ransel 0/1, barang tidak dapat dibagi — pendekatan rakus gagal, sehingga DP diperlukan. Pewawancara menggunakan perbedaan ini untuk menguji apakah Anda mengetahui kapan pendekatan rakus dapat diterapkan. Jika ditanya tentang varian pecahan, segera sebutkan pendekatan rakus dengan pengurutan; jika 0/1, gunakan DP.
# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total = 0
for v, w in items:
if W >= w:
total += v; W -= w
else:
total += v * (W / w); break
return total
print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))Kompleksitas Waktu Pseudopolinomial
Ransel 0/1 adalah NP-lengkap, tetapi kita dapat menyelesaikannya dalam waktu O(nW). Kontradiksi ini teratasi karena O(nW) bersifat pseudopolinomial: W adalah sebuah nilai, bukan ukuran input. Representasi biner W memerlukan O(log W) bit, sehingga kompleksitas sebenarnya adalah O(n × 2^(log W)), yang bersifat eksponensial terhadap ukuran input. Ketika W kecil (misalnya, 10⁴), DP ini praktis; ketika W dapat mencapai 10⁹, kita memerlukan pendekatan yang berbeda.
Pertanyaan Lanjutan Pewawancara: Kapasitas Besar
Jika pewawancara menetapkan W yang sangat besar (misalnya, 10⁹) tetapi n kecil, DP standar tidak dapat digunakan. Alternatifnya meliputi: (1) pendekatan bertemu di tengah dalam waktu O(2^(n/2) × n), (2) aproksimasi rakus untuk varian pecahan, atau (3) pencabangan dan pembatasan. Untuk sebagian besar soal wawancara dengan W <= 10⁵, DP 1D dengan iterasi mundur adalah jawaban yang diharapkan.
Pendekatan Bertemu di Tengah untuk Kapasitas Besar
Ketika W sangat besar tetapi n kecil (misalnya, n=40), DP standar O(nW) tidak layak digunakan, tetapi pemeriksaan semua kemungkinan 2^n terlalu lambat. Pendekatan bertemu di tengah membagi barang menjadi dua bagian, menghitung semua 2^(n/2) himpunan bagian untuk setiap bagian, lalu memasangkannya secara optimal. Urutkan satu bagian berdasarkan bobot, kemudian untuk setiap himpunan bagian dari bagian lainnya gunakan pencarian biner untuk menemukan pasangan terbaik dalam batas kapasitas. Algoritme ini berjalan dalam O(2^(n/2) × n) — praktis untuk n hingga 40.
Uji Cepat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: DP ransel 0/1 memiliki keadaan dp[i][c] yang merepresentasikan nilai maksimum dengan i barang dan kapasitas c, relasi rekurensinya memilih untuk melewati atau mengambil setiap barang, dan optimasi ruang 1D mengiterasi kapasitas dari kanan ke kiri untuk mencegah penghitungan barang dua kali. Berikutnya, kita akan mengeksplorasi ransel tak terbatas, tempat barang dapat digunakan kembali, dan menerapkannya pada Penukaran Koin II.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Knapsack 0/1 dan Optimasi Ruang” gratis?
Ya — teks lengkap “Knapsack 0/1 dan Optimasi Ruang” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Knapsack 0/1 dan Optimasi Ruang”?
Turunkan relasi rekurensi knapsack 0/1, isi tabel 2D, lalu sederhanakan menjadi array 1D dengan mengiterasi kapasitas secara terbalik Kamu berlatih Coding Interview Prep 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 Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep 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 dan Optimasi Ruang” 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 Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep 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 dan Optimasi Ruang
- Knapsack Tak Terbatas dan Coin Change II
- Jumlah Subhimpunan Sama untuk Partisi
- Jumlah Target dengan Tanda Positif dan Negatif