Pemrograman DinamisLanjutFase E–FE1E5

Knapsack 0/1 (Dynamic Programming)

Knapsack 0/1 memilih subset barang agar nilai total maksimum tanpa melewati batas kapasitas. Dynamic Programming mengisi tabel dp[barang][kapasitas]: tiap sel = max(LEWATI barang ini, AMBIL barang ini + nilai sisa kapasitas). Telusur balik dari pojok tabel menunjukkan barang mana yang terpilih.

Contoh kasus

Alokasi anggaran atau ruang terbatas: memilih kombinasi proyek atau muatan dengan keuntungan terbesar di bawah batas biaya atau berat.

Silabus

Knapsack 0/1 memilih kombinasi barang bernilai maksimum tanpa melewati batas kapasitas, tiap barang diambil utuh atau tidak sama sekali.

Tujuan Belajar

·Memahami pilihan ambil-atau-lewati untuk tiap barang
·Menjelaskan cara tabel dp[barang][kapasitas] dibangun
·Menerapkan telusur balik untuk tahu barang mana yang terpilih

Cara Kerja

·Buat tabel dp berdasarkan barang (baris) dan sisa kapasitas (kolom)
·Untuk tiap sel, hitung nilai bila barang ini DILEWATI
·Hitung juga nilai bila barang ini DIAMBIL plus nilai sisa kapasitas
·Ambil yang lebih besar di antara dua pilihan itu
·Telusuri balik dari pojok tabel untuk menemukan barang yang dipilih

Prasyarat

·Tabel 2D (matriks)
·Coin Change (DP)

Contoh Nyata

·Memilih barang bawaan ke dalam tas dengan berat terbatas saat liburan
·Alokasi uang jajan terbatas untuk kombinasi barang paling berguna
·Menentukan muatan paket kurir agar nilai kiriman maksimal di bawah batas berat

Kompleksitas O(jumlah barang x kapasitas)