Tuliskan dalam Notasi Pseudocode Algoritma yang Sesuai untuk Menyelesaikan Permasalahan Rational Knapsack
Tuliskan dalam notasi pseudocode algoritma yang sesuai untuk menyelesaikan permasalahan rational knapsack menggunakan strategi yang Anda pilih pada bagian nomor 1!
Jawaban:
Notasi pseudocode algoritma yang sesuai untuk menyelesaikan permasalahan rational knapsack menggunakan dynamic programming) adalah:
function rationalKnapsack(weights, values, capacity):
n = length(weights) // Jumlah item yang tersedia
dp = array of size (n+1) x (capacity+1) // Tabel DP untuk menyimpan hasil submasalah
// Inisialisasi nilai awal tabel DP
for w in 0 to capacity:
dp[0][w] = 0
// Proses dinamis programming
for i from 1 to n:
for w from 0 to capacity:
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
else:
dp[i][w] = dp[i-1][w]
// Menyimpan hasil nilai optimal
optimalValue = dp[n][capacity]
// Mengembalikan nilai optimal
return optimalValue
Pembahasan:
- Fungsi rationalKnapsack menerima tiga parameter: weights (array berisi bobot item), values (array berisi nilai item), dan capacity (kapasitas knapsack).
- Variabel n menyimpan jumlah item yang tersedia.
- Membuat tabel DP dengan ukuran (n+1) x (capacity+1) dan menyimpannya dalam variabel dp.
- Melakukan inisialisasi nilai awal tabel DP, dengan setiap elemen dp[0][w] diatur menjadi 0 karena belum ada item yang dipertimbangkan.
- Melakukan proses dynamic programming dengan dua loop bersarang. Loop pertama (for i from 1 to n) digunakan untuk mengiterasi setiap item yang tersedia. Loop kedua (for w from 0 to capacity) digunakan untuk mengiterasi setiap kapasitas yang mungkin.
- Pada setiap langkah, dilakukan pengecekan apakah bobot item saat ini (weights[i-1]) lebih kecil atau sama dengan kapasitas (w) yang sedang dipertimbangkan. Jika iya, maka kita membandingkan nilai antara tidak memasukkan item ini (dp[i-1][w]) dengan memasukkan item ini (values[i-1] + dp[i-1][w-weights[i-1]]). Pilih nilai maksimum dari kedua opsi tersebut dan simpan di dp[i][w].
- Jika bobot item saat ini lebih besar dari kapasitas yang sedang dipertimbangkan, maka tidak memasukkan item ini ke dalam knapsack, sehingga nilai dp[i][w] sama dengan dp[i-1][w].
- Setelah selesai iterasi, nilai optimal yang didapatkan disimpan dalam variabel optimalValue dengan mengambil nilai dp[n][capacity].
- Mengembalikan optimalValue sebagai hasil akhir.