Diberikan sejumlah item dengan berat dan nilai tertentu, serta sebuah ransel dengan kapasitas tertentu. Tugas Anda adalah memilih item-item untuk dimasukkan ke dalam ransel sehingga nilai total item-item yang dipilih maksimal, tanpa melebihi kapasitas ransel.
- Setiap item memiliki jumlah maksimal yang dapat dipilih.
- Algoritma backtracking harus digunakan untuk menyelesaikan masalah ini. Tidak boleh menggunakan greedy algorithm.
- Setiap kombinasi item yang memungkinkan harus dieksplorasi menggunakan backtracking.
Sebuah daftar item, masing-masing item memiliki:
- Berat (𝑤𝑖): Berat item ke-i.
- Nilai (𝑣𝑖): Nilai item ke-i.
- Jumlah maksimal (𝑚𝑖): Jumlah maksimal item ke-i yang bisa dipilih.
- Kapasitas maksimal ransel (W).
Diberikan daftar 8 item berikut:
Kapasitas ransel (W): 20 kg.
- Tentukan kombinasi item yang bisa dipilih sehingga nilai total item maksimal tanpa melebihi kapasitas ransel 20 kg.
- Tentukan berapa unit dari masing-masing item yang dipilih untuk mencapai nilai maksimal tersebut.
- Kombinasi item dan jumlah yang dipilih.
- Nilai maksimum yang bisa didapatkan.
- Eksplorasi semua kemungkinan kombinasi item. Untuk setiap item, pilih dari 0 hingga jumlah maksimal yang diperbolehkan.
- Setiap kali memilih suatu jumlah untuk item, periksa apakah kapasitas ransel melebihi batas. Jika melebihi, lakukan backtrack.
- Jika kapasitas tidak terlampaui, lanjutkan ke item berikutnya.
- Simpan solusi terbaik (nilai tertinggi) yang ditemukan selama proses eksplorasi.
- Mulai dengan ransel kosong dan kapasitas 20 kg.
- Untuk setiap item, pilih antara 0 hingga jumlah maksimal item tersebut, cek apakah masih memungkinkan berdasarkan kapasitas ransel.
- Jika memungkinkan, tambahkan nilai item ke dalam ransel, dan periksa apakah nilai total lebih baik dari solusi sebelumnya.
- Jika kapasitas ransel terlampaui, kembalikan (backtrack) dan coba opsi lain.
- Setelah semua kombinasi dicoba, kembalikan kombinasi item yang memberikan nilai maksimal.