My first Magazine pemrograman-kompetitif-dasar | Page 79

7.2 Contoh-contoh DP Sederhana
Jika tersedia 5 buah barang sebagai berikut:
Nomor Barang
1
2
3
4
5
Harga
6
5
4
6
4
Berat
5
4
3
7
4
Jika kita memiliki kapasitas sebesar 14, solusi terbaik adalah mengambil barang ke 1, 2,
dan 5. Total harga yang diperoleh adalah 6 + 5 + 4 = 15.
Perhatikan bahwa untuk setiap barang, terdapat dua pilihan yang dapat kita lakukan: ambil
atau tinggalkan. Jika barang tersebut diambil, kapasitas tas kita berkurang dan harga barang yang
kita dapatkan bertambah. Jika barang tersebut tidak diambil, tidak terjadi perubahan. Dengan
demikian, kita bisa memformulasikan sebuah fungsi d p(i, c) sebagai jumlah harga maksimum
yang mungkin diperoleh, jika kita hanya mempunyai barang ke-1 sampai ke-i dan sisa kapasitas
tas kita adalah c gram. Untuk menghitung fungsi d p(i, c), kita akan mencoba apakah kita akan
memasukkan barang ke-i ke tas atau tidak.
Jika i = 0, maka berarti tidak ada barang yang tersedia. Ini berarti d p(i, c) = 0. Kasus ini
menjadi base case . Selain kasus base case , untuk setiap i dan c, kita memiliki paling banyak dua
pilihan:
• Kasus 1: Mengambil barang ke-i
Jika kita memasukkan barang ke-i ke tas, maka kita akan menyisakan barang ke-1 sampai
ke-(i − 1) dan sisa kapasitas tas menjadi c − w i . Harga barang yang didapatkan pada kasus
ini adalah d p(i − 1, c − w i ) ditambah dengan harga yang kita peroleh pada barang ke-i, atau
dapat dituliskan d p(i, c) = d p(i − 1, c − w i ) + v i . Karena kita memiliki kapasitas tas c, kasus
ini hanya boleh dipertimbangkan jika c ≥ w i .
• Kasus 2: Tidak mengambil barang ke-i
Jika kita tidak memasukkan barang ke-i ke tas, maka kita akan menyisakan barang ke-1
sampai ke-(i − 1) dan sisa kapasitas tas masih tetap c. Harga barang didapatkan pada
kasus ini adalah d p(i − 1, c), tanpa tambahan apapun (kita tidak mengambil barang ke-i),
atau dapat dituliskan d p(i, c) = d p(i − 1, c).
Dari kedua pilihan keputusan tersebut, kita tertarik dengan pilihan yang menghasilkan nilai
terbesar. Dengan demikian d p(i, c) dapat dirumuskan sebagai berikut:

i = 0
 0,
d p(i − 1, c),
i > 0 ∧ c < w i
d p(i, c) =

max(d p(i − 1, c − w i ) + v i , d p(i − 1, c)), i > 0 ∧ c ≥ w i
Analisis Kompleksitas
Terdapat O(N) nilai berbeda untuk nilai i dan O(G) nilai berbeda untuk nilai c pada d p(i, c).
Dibutuhkan O(1) untuk menghitung d p(i, c). Sehingga untuk menghitung seluruh nilai d p(i, c)
untuk seluruh i dan c dibutuhkan waktu O(NG).
69