[Opsional] Tuliskan dalam Notasi Pseudocode Algoritma yang Sesuai Untuk Menyelesaikan Permasalahan 0-1 Knapsack

-

[Opsional] Tuliskan dalam notasi pseudocode algoritma yang sesuai untuk menyelesaikan permasalahan 0-1 knapsack menggunakan strategi yang Anda pilih pada bagian nomor 2!

Jawaban:

Notasi pseudocode algoritma yang sesuai untuk menyelesaikan permasalahan 0-1 knapsack menggunakan strategi Dynamic Programming:

function knapsack(weights, values, W, n):
    // weights: array berisi bobot dari setiap item
    // values: array berisi nilai dari setiap item
    // W: kapasitas maksimum knapsack
    // n: jumlah total item

    // Inisialisasi tabel DP dengan nilai 0
    DP <- array[n+1][W+1]
    for i <- 0 to n do:
        for w <- 0 to W do:
            if i = 0 or w = 0 then:
                DP[i][w] <- 0
            else if weights[i-1] <= w then:
                // Memilih nilai maksimum antara mengambil item ke-i atau tidak mengambilnya
                DP[i][w] <- max(values[i-1] + DP[i-1][w-weights[i-1]], DP[i-1][w])
            else:
                // Tidak dapat mengambil item ke-i karena bobotnya lebih besar dari kapasitas knapsack
                DP[i][w] <- DP[i-1][w]

    // Mengembalikan nilai maksimum yang dapat dicapai
    return DP[n][W]

Pembahasan:
  1. Membuat tabel DP dengan ukuran (n+1) x (W+1), di mana n adalah jumlah total item dan W adalah kapasitas maksimum knapsack.
  2. Inisialisasi nilai tabel DP dengan 0.
  3. Melakukan iterasi dari i = 1 hingga n dan w = 1 hingga W untuk mengisi tabel DP.
  4. Jika item ke-i memiliki bobot yang lebih kecil atau sama dengan w (kapasitas yang sedang dipertimbangkan), kita membandingkan nilai jika item tersebut diambil dengan tidak mengambilnya. Nilai ini diperoleh dengan menjumlahkan nilai item ke-i dengan nilai maksimum yang bisa didapatkan dari sisa kapasitas w setelah mengambil item tersebut, yaitu DP[i-1][w-weights[i-1]]. Kemudian, kita membandingkan nilai tersebut dengan nilai jika item ke-i tidak diambil, yaitu DP[i-1][w]. Kami memilih nilai maksimum dari kedua pilihan tersebut.
  5. Jika bobot item ke-i lebih besar dari w, artinya item tersebut tidak dapat diambil, sehingga nilai DP[i][w] sama dengan nilai DP[i-1][w].
  6. Setelah selesai melakukan iterasi, nilai maksimum yang dapat dicapai adalah DP[n][W].