Penerapan Algoritma DFS dalam Kasus Knapsack (Pemilihan Barang ke Tas)
Kasus: Suatu hari kamu ingin bepergian dengan tas berkapasitas 10 kg . Di rumah ada 5 barang dengan berat dan nilai berbeda: Barang 1: Berat 6 kg , Nilai 30 Barang 2: Berat 3 kg , Nilai 14 Barang 3: Berat 4 kg , Nilai 16 Barang 4: Berat 2 kg , Nilai 9 Barang 5: Berat 5 kg , Nilai 20 Karena kapasitas tas hanya 10 kg , kamu harus pintar memilih kombinasi barang agar total nilai maksimal tetapi tidak melebihi 10 kg . Untuk mencari solusinya, kita gunakan DFS (Depth-First Search) . DFS akan menelusuri semua kemungkinan kombinasi barang (ambil / tidak ambil), lalu memilih yang terbaik. Kode Program : import java.util.HashMap; public class KnapsackDFSHashMap { static int maxValue = 0; static int bestWeight = 0; static String bestChoice = ""; public static void main(String[] args) { HashMap<Integer, int[]> items = new HashMap<>(); items.p...