Level	Intermediate
Type	Dynamic Programming
Requirement	Introduction to Dynamic Programming Introduction to Greedy
Similar	Introduction to Dynamic Programming Matrix Chain Multiplication (MCM) Longest Increasing Subsequence (LIS) Coin Change Problem

Sekarang kita akan membahas soal klasik yaitu Knapsack Zero One

Penjelasan Knapsack Zero One

Soal knapsack mempunyai banyak tipe, salah satunya adalah knapsack zero one.
Sebelum mulai kita harus mengerti dulu problem knapsack seperti apa.
Bayangkan kalau anda adalah seorang pencuri dan anda sedang merampok satu toko.
Anda mempunyai satu kantong/tas (knapsack) buat mencuri barang - barang tersebut.
Tas anda hanya bisa menampung C kilogram total berat benda, dan tiap benda yang akan anda ambil memiliki dua property yaitu berat (w) dan harga/nilai (v).

Tentu sebagai pencuri yang sejati anda ingin memaksimalkan total harga benda yang akan anda curi. Tetapi tentunya total berat benda harus kurang atau sama dengan kapasitas tas kita.

Nah untuk knapsack zero one, hanya sedikit perbedaannya, yaitu tipe barang yang bisa kita curi ada tepat N. Dan tiap tipe barang hanya memiliki satu stok. Karena itu disebut zero one, bisa kita ambil, atau tidak sama sekali.

Dan beberapa variasi lain dari knapsack adalah, fractional knapsack, knapsack yang gak zero one (gak tau istilahnya).

Analisis Problem

Untuk beberapa orang yang belum terlalu mengenal DP, mereka sering sekali secara tidak sadar menyelesaikan problem ini dengan Greedy. Tapi perlu diketahui kemungkinan beberapa soal knapsack zero one bisa diselesaikan dengan Greedy, tapi soal tersebut harus memiliki property khusus yang membuat soal itu bisa di Greedy. (dan aku pun masih belum benar - benar tahu property itu seperti apa ==a..., kalau anda tahu let me know it, comment below :D)

Andaikan ada soal berikut
N = 10
W = 20
data =

indeks	w	v
0	1	1
1	2	1
2	1	2
3	3	1
4	4	3
5	2	7
6	6	2
7	3	6
8	5	5
9	7	3

Ada beberapa approach greedy yang biasanya digunakan, walaupun cara tersebut tidak akan memberikan solusi yang benar.

Berdasarkan Value Paling Besar, Weight Paling Kecil O(N log N)

Jadi jika data tersebut di sorting berdasarkan value yang paling besar, kemudian jika value tersebut sama, maka berdasar weight yang lebih kecil, maka akan menghasilkan urutan indeks
5 7 8 4 9 2 6 0 1 3
Dan akan mengambil langsung dari depan jika barang tersebut masih bisa dimasukkan ke dalam tas.
Jadi proses pengambilannya seperti ini

1. C = 20, karena w[5] <= C, maka diambil, V = 7, C = 18
2. C = 18, karena w[7] <= C, maka diambil, V = 13, C = 15
3. C = 15, karena w[8] <= C, maka diambil, V = 18, C = 10
4. C = 10, karena w[4] <= C, maka diambil, V = 21, C = 6
5. C = 6, karena w[9] > C, maka tidak diambil, V = 21, C = 6
6. C = 6, karena w[2] <= C, maka diambil, V = 23, C = 5
7. C = 5, karena w[6] > C, maka tidak diambil, V = 23, C = 5
8. C = 5, karena w[0] <= C, maka diambil, V = 24, C = 4
9. C = 4, karena w[1] <= C, maka diambil, V = 25, C = 2
10. C = 2, karena w[3] > C, maka tidak diambil, V = 25, C = 2

Jadi yang akan kita peroleh dengan greedy semacam ini adalah V = 25. (kalau tidak salah hitung).
Apakah ini jawaban yang optimal? Kelihatannya begitu, tapi kita coba dengan approach lain.

Berdasarkan Weigh Paling Kecil, Value Paling Besar O(N log N)

Jadi jika data tersebut di sorting berdasarkan weight yang paling kecil, kemudian jika weight tersebut sama, maka berdasar value yang lebih besar, maka akan menghasilkan urutan indeks
2 0 5 1 7 3 4 8 6 9
Dilakukan approach ini dengan berpikiran bahwa jika kita mengambil benda - benda dengan berat yang kecil, kita akan dapat mengambil lebih banyak benda sehingga berharap bahwa semakin banyak benda semakin besar pula total valuenya.

1. C = 20, karena w[2] <= C, maka diambil, V = 2, C = 19
2. C = 19, karena w[0] <= C, maka diambil, V = 3, C = 18
3. C = 18, karena w[5] <= C, maka diambil, V = 10, C = 16
4. C = 16, karena w[1] <= C, maka diambil, V = 11, C = 14
5. C = 14, karena w[7] <= C, maka diambil, V = 17, C = 11
6. C = 11, karena w[3] <= C, maka diambil, V = 18, C = 8
7. C = 8, karena w[4] <= C, maka diambil, V = 21, C = 4
8. C = 4, karena w[8] > C, maka tidak diambil, V = 21, C = 4
9. C = 4, karena w[6] > C, maka tidak diambil, V = 21, C = 4
10. C = 4, karena w[9] > C, maka tidak diambil, V = 21, C = 4

Dan ternyata dengan cara ini diperoleh V = 21. Dan ternyata lebih buruk dari sebelumnya. Karena itu Greedy tidak bisa kita pakai disini. Kalau dalam suatu soal anda bisa buktikan itu bisa digunakan Greedy, baru anda gunakan Greedy.

Tetapi kadang - kadang orang tanpa membuktikannya langsung memakai Greedy, kalau tidak ACCEPTED, artinya terbukti Greedy tersebut tidak bisa dilakukan.

Berdasarkan Density O(N log N)

Jadi dalam approach ini, kita mengurutkan data berdasarkan harga per kilogram, atau densitynya. Jadi kita mengurutkan berdasarkan V/W dari paling besar.
Kira - kira caranya sama seperti diatas, tetapi saya malas membahasnya, karena tujuan sebenarnya post ini adalah membahas DP dari Knapsack itu sendiri. *swt

Brute Force O(N*2^N)

Cara mem-bruteforce DP ini, lumayan agak ribet kodingnya dibandingkan cara DP-nya. Konsep bruteforcenya memang mudah, konsepnya adalah kita mencoba semua kemungkinan cara untuk memilih barang.
Misalkan sepuluh barang diatas, ada suatu konfigurasi yang bisa dilambangkan dengan 0 dan 1, 0 artinya barang tidak diambil, 1 artinya barang diambil.
Misalkan 0110011010, artinya barang ke 1,2,5,6,8 diambil, sedangkan barang lainnya tidak diambil.

Setiap konfigurasi nantinya akan kita cek apakah jika barang - barang tersebut diambil akan muat di tas, ini memerlukan O(N), jika muat, maka kita simpan total value dari konfigurasi tersebut.
Lakukan ini ke semua konfigurasi, dan cari max total value yang mungkin.
Total semua konfigurasi yang mungkin adalah O(2^N), jadi kompleksitasnya adalah O(N * 2^N).

Untuk mengoding dengan bruteforce secara iteratif (menggunakan loop saja tidak menggunakan rekursif) anda harus mengerti dulu pengoperasian bit didalam integer yang mungkin akan dibahas dalam post lainnya.

Dynamic Programming O(N*C)

Untuk DP sendiri lumayan mudah di koding jika sudah mengerti konsepnya.
Jadi sekarang kita ingin melakukan fungsi rekursif.
Anggap fungsi f(n, c) akan mengembalikan total v maksimum dari benda ke n sampai benda ke N-1, dengan sisa kapasitas tas sebesar c.

Misalkan f(5, 15) itu artinya total v maksimum (nilai yang kita cari) jika problem kita hanya ada benda ke 5, 6, 7, 8, 9, dan kapasitas tas kita sekarang itu masih ada 15. (artinya kita bisa masukkin beberapa benda dari benda 5 sampai 9, kalau total beratnya gak lebih dari 15).

Tentunya yang kita ingin cari adalah f(0, C), yaitu total v maksimum dari benda ke 0 sampai benda terakhir yaitu benda ke 9, dengan kapasitas yang ada di tas itu adalah C (input problem).

Jika anda sudah mengerti definisi dari f(n, c), maka gampangnya kita bisa mendefinisikan rekurensnya terlebih dahulu.

Jika kita posisi kita ada di 'n', kita bisa menentukan apakah kita ingin mengambil benda ke n tersebut atau tidak, jika kita mengambil artinya value total yang mungkin kita dapatkan adalah v[n] + f(n+1, c-w[n]), maksudnya adalah harga benda tersebut ditambah dengan total v maksimum yang mungkin kita peroleh dari benda selanjutnya dengan kapasitas yang sudah kita kurang dengan berat benda sekarang.
Tetapi bisa saja jika kita tidak mengambil benda itu, malahan akan memperbesar total v maksimum kita, sehingga jika kita tidak ambil maka total v yang bisa kita dapatkan adalah f(n+1, c).
Dari kedua itu, kita cari mana yang maksimum.
Note : sebelum kita mengambil benda, kita harus pastikan bahwa kita bisa mengambil benda itu, yaitu memenuhi syarat w[n] <= c. Jadi rumus rekurens bisa kita tentukan sebagai berikut

f(n, c) = max(((w[n] <= c)? (v[n] + f(n+1, c-w[n])) : 0), f(n+1, c));

Yaitu mencari maksimum antara ambil (v[n] + f(n+1, c-w[n])) atau tidak (f(n+1, c)).
Jika ternyata w[n] > c, maka pasti tidak bisa diambil, maka kita tentuin jadi 0.

Sekarang jika sudah paham, kita berlanjut ke base case nya.
Base casenya adalah jika ternyata kita sudah sampai ujung, n == N, yaitu dia tidak menunjukkan ke barang apapun. (ingat barang kita hanya sampai ke N-1, karena indeks mulai dari 0).
Jika n == N, maka nilainya 0, karena tidak bisa mengambil barang apapun lagi, artinya total v maksimum pasti 0 juga.

f(N, c) = 0;

Rumus lengkapnya adalah

f(n, c) = max(((w[n] <= c)? (v[n] + f(n+1, c-w[n])) : 0), f(n+1, c));
f(N, c) = 0;

Jika sudah menemukan rumusnya, harusnya kodingnya tinggal merem aja LOL. Jadi pertama - tama kita koding rekursifnya dulu.

int f(int n, int c)
{
  int hasil;
  if(n == N)
  {
    hasil = 0;
  } else
  {
    hasil = 0;

    // ambil
    if(w[n] <= c) hasil = max(hasil, v[n] + f(n+1, c-w[n]));
    
    // nggak ambil
    hasil = max(hasil, f(n+1, c));
  }
  return hasil;
}

Kode di atas belum menjadi DP, itu hanya rekursif biasa. Dan bisa dikatakan itu masih bruteforce. Jika dilihat, dia rekursif diatas akan mengunjungi semua konfigurasi yang mungkin , sehingga jawaban yang dihasilkan pasti benar. Tapi kompleksitas kode diatas adalah O(2^N), karena setiap state mengunjungi dua state lainnya, dan kedalaman yang paling dalam adalah N. Untuk menjadikan DP, harusnya gampang banget, tinggal diginiin

int f(int n, int c)
{
  int& hasil = memo[n][c];
  if(hasil == -1)
  {
    if(n == N)
    {
      hasil = 0;
    } else
    {
      hasil = 0;
  
      // ambil
      if(w[n] <= c) hasil = max(hasil, v[n] + f(n+1, c-w[n]));
      
      // nggak ambil
      hasil = max(hasil, f(n+1, c));
    }
  }
  return hasil;
}

Udah digituin aja.
Kompleksitasnya menjadi O(N*C), untuk mengisi semua state diperlukan O(N*C), dan untuk tiap fungsi memerlukan hanya O(1), sehingga totalnya yaitu O(N*C * 1) = O(N*C).
Untuk yang nanya int& itu apaan.
Itu anggap aja sebagai shortcut dalam menuliskan memo[n][c]. Jika kita menuliskan variable hasil, anggap saja dia akan otomatis diganti dengan memo[n][c], sehingga kita tidak perlu menuliskan memo[n][c] yang panjang itu berkali - kali.

Dan perlu diketahui kompleksitas O(N*C) sebenarnya bisa dikatakan program akan berjalan lebih cepat dari itu, karena dalam penggunaan DP ini, dia tidak menghitung semua state yang ada. Paling banyak dia akan menghitung N*2^N state saja. Sehingga kompleksitas yang agak tepatnya walaupun agak aneh itu adalah O(N*min(C, 2^N)), tapi untuk disederhanakan O(N*C) aja lah.

Mungkin itu dulu, ntah mengapa post ini menjadi panjang banget.
Untuk sekedar info soal ini bisa dipakai DP Bottom Up juga, tapi sebenarnya jika sudah menemukan DP Top Down bisa diubah dengan mudah ke DP Bottom Up, jadi akan dibahas di post lain.

That's it...
Ciao~...