Dynamic ProgrammingLanjutFase E–FE1E5

0/1 KNAPSACK

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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

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

Real-World Uses

·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

Complexity O(jumlah barang x kapasitas)