0/1 Perbaikan Masalah Knapsack menggunakan Contoh Pemrograman Dinamis

Oleh: Sarah Chen Sarah Chen
Hours Updated

Apa Masalah Ransel itu?

Masalah Ransel algoritma adalah masalah yang sangat membantu dalam kombinatorik. Di supermarket terdapat n paket (n ≤ 100) paket i mempunyai berat W[i] ≤ 100 dan nilai V[i] ≤ 100. Seorang pencuri membobol supermarket, pencuri tidak boleh membawa beban melebihi M (M ≤ 100 ). Permasalahan yang harus dipecahkan disini adalah: paket manakah yang akan diambil oleh pencuri untuk mendapatkan nilai tertinggi?

Memasukkan:

  • Berat maksimum M dan jumlah paket n.
  • Array dengan bobot W[i] dan nilai terkait V[i].

Keluaran:

  • Maksimalkan nilai dan bobot yang sesuai dalam kapasitas.
  • Paket mana yang akan diambil pencurinya.

Algoritma Knapsack dapat dibagi lagi menjadi dua jenis:

  • Masalah Knapsack 0/1 menggunakan pemrograman dinamis. Pada jenis algoritma Knapsack ini, setiap paket dapat diambil atau tidak. Selain itu, pencuri tidak boleh mengambil sebagian dari paket yang diambil atau mengambil paket lebih dari satu kali. Tipe ini dapat diselesaikan dengan Pendekatan Pemrograman Dinamis.
  • Algoritma masalah pecahan Knapsack. Tipe ini dapat diatasi dengan Strategi Greedy.

Cara Menyelesaikan Masalah Knapsack Menggunakan Pemrograman Dinamis disertai Contoh

Dalam strategi membagi dan menaklukkan, Anda membagi masalah yang ingin diselesaikan menjadi sub-masalah. Submasalah tersebut dibagi lagi menjadi submasalah yang lebih kecil. Tugas itu akan berlanjut hingga Anda mendapatkan submasalah yang dapat diselesaikan dengan mudah. Namun, dalam proses pembagian tersebut, Anda mungkin menemui masalah yang sama berkali-kali.

Ide dasar dari pemrograman dinamis Knapsack adalah menggunakan tabel untuk menyimpan solusi dari submasalah yang diselesaikan. Jika Anda menghadapi submasalah lagi, Anda hanya perlu mengambil solusi yang ada di tabel tanpa harus menyelesaikannya lagi. Oleh karena itu, algoritma yang dirancang oleh pemrograman dinamis sangat efektif.

Selesaikan Masalah Knapsack menggunakan Pemrograman Dinamis

Untuk menyelesaikan masalah dengan pemrograman dinamis, Anda perlu melakukan tugas-tugas berikut:

  • Temukan solusi dari submasalah terkecil.
  • Temukan rumus (atau aturan) untuk membangun solusi submasalah melalui solusi submasalah terkecil sekalipun.
  • Buat tabel yang menyimpan solusi submasalah. Kemudian hitung solusi submasalah sesuai dengan rumus yang ditemukan dan simpan ke tabel.
  • Dari sub-masalah yang terselesaikan, Anda menemukan solusi dari masalah aslinya.

Analisis Masalah Knapsack 0/1

Saat menganalisis masalah 0/1 Knapsack menggunakan pemrograman Dinamis, Anda dapat menemukan beberapa poin penting. Nilai algoritma knapsack bergantung pada dua faktor:

  1. Berapa banyak paket yang sedang dipertimbangkan
  2. Sisa berat yang dapat disimpan oleh ransel.

Oleh karena itu, Anda memiliki dua besaran variabel.

Dengan pemrograman dinamis, Anda memiliki informasi berguna:

  1. fungsi tujuan akan bergantung pada dua besaran variabel
  2. tabel pilihan akan menjadi tabel 2 dimensi.

Jika memanggil B[i][j] adalah nilai maksimum yang mungkin dengan memilih paket {1, 2, …, i} dengan batas bobot j.

  • Nilai maksimum bila dipilih dalam n paket dengan batas berat M adalah B[n][M]. Dengan kata lain: Jika ada i paket yang harus dipilih, B[i][j] adalah bobot optimal bila bobot maksimum ransel adalah j.
  • Bobot optimal selalu kurang dari atau sama dengan bobot maksimum: B[i][j] ≤ j.

Misal: B[4][10] = 8. Artinya pada kasus optimal, berat total paket yang dipilih adalah 8, bila ada 4 paket pertama yang dapat dipilih (paket ke-1 hingga ke-4) dan berat maksimum ranselnya adalah 10. Keempat item tersebut tidak perlu dipilih semua.

ARTIKEL TERKAIT

Rumus Menghitung B[i][j]

Masukan, Anda tentukan:

  • W[i], V[i] pada gilirannya merupakan bobot dan nilai paket i, di mana i Rumus Menghitung B[i][j]{1, …, n}.
  • M adalah berat maksimum yang dapat dibawa oleh ransel.

Dalam hal hanya memiliki 1 paket untuk dipilih. Anda menghitung B[1][j] untuk setiap j: yang berarti berat maksimum ransel ≥ berat paket pertama

B[1][j] = W[1]

Dengan batasan bobot j, pemilihan optimal antar paket {1, 2, …, i – 1, i} yang memiliki nilai terbesar akan memiliki dua kemungkinan:

  • Jika paket i tidak dipilih, B[i][j] adalah nilai maksimum yang mungkin diperoleh dengan memilih di antara paket {1, 2, …, i – 1} dengan batas bobot j. Kamu punya:
B[i][j] = B[i – 1][j]
  • Jika paket i dipilih (tentu saja hanya mempertimbangkan kasus ini ketika W[i] ≤ j) maka B[i][j] sama dengan nilai V[i] dari paket i ditambah nilai maksimum dapat diperoleh dengan memilih di antara paket {1, 2, …, i – 1} dengan batasan berat (j – W[i]). Artinya, berdasarkan nilai yang Anda miliki:
B[i][j] = V[i] + B[i – 1][j – W[i]]

Karena pembuatan B[i][j], yang merupakan nilai maksimum yang mungkin, B[i][j] akan menjadi nilai maksimal dari 2 nilai di atas.

Dasar Pemrograman Dinamis

Jadi, Anda harus mempertimbangkan apakah lebih baik memilih paket i atau tidak. Dari sana Anda mendapatkan rumus rekursif sebagai berikut:

B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]

Sangat mudah untuk melihat B[0][j] = nilai maksimum yang mungkin dengan memilih dari 0 paket = 0.

Hitung Tabel Pilihan

Anda membuat tabel opsi berdasarkan rumus rekursif di atas. Untuk memeriksa apakah hasilnya benar (jika tidak persis, Anda membangun kembali fungsi tujuan B[i][j]). Melalui pembuatan fungsi tujuan B[i][j] dan tabel opsi, Anda akan mengarahkan penelusuran.

Tabel opsi B mencakup n + 1 baris, M + 1 kolom,

  • Pertama, diisi dengan dasar pemrograman dinamis: Baris 0 memuat semua angka nol.
  • Dengan menggunakan rumus rekursif, gunakan baris 0 untuk menghitung baris 1, gunakan baris 1 untuk menghitung baris 2, dst.…sampai semua baris dihitung.
Hitung Tabel Pilihan
Tabel Pilihan

Jejak

Saat menghitung tabel opsi, Anda tertarik pada B[n][M] yang merupakan nilai maksimum yang diperoleh saat memilih semua n paket dengan batas bobot M.

  • If B[n][M] = B[n – 1][M] maka paket n tidak dipilih, Anda menelusuri B[n – 1][M].
  • If B[n][M] ≠ B[n – 1][M], Anda melihat bahwa pilihan optimal memiliki paket n dan jejak B[n – 1][M – W[n]].

Lanjutkan menelusuri hingga mencapai baris 0 pada tabel opsi.

Algoritma untuk Mencari Tabel Pilihan untuk Menemukan Paket Terpilih

Catatan: Jika B[i][j] = B[i – 1][j], paket i tidak dipilih. B[n][W] adalah nilai total paket optimal yang dimasukkan ke dalam knapsack.

Langkah-langkah untuk menelusuri:

  • Langkah 1: Dimulai dari i = n, j = M.
  • Langkah 2: Lihat pada kolom j, dari bawah ke atas, terdapat garis i sehingga B[i][j] > B[i – 1][j]. Tandai paket yang dipilih i: Pilih [i] = true;
  • Langkah 3: j = B[i][j] – W[i]. Jika j > 0, lanjut ke langkah 2, jika tidak, lanjut ke langkah 4
  • Langkah 4: Berdasarkan tabel pilihan untuk mencetak paket yang dipilih.

Java Kode

public void knapsackDyProg(int W[], int V[], int M, int n) {
	int B[][] = new int[n + 1][M + 1];
	
	for (int i=0; i<=n; i++)
		for (int j=0; j<=M; j++) {
			B[i][j] = 0;
		}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= M; j++) {
			B[i][j] = B[i - 1][j];
			
			if ((j >= W[i-1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
				B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1]; 
			}
			
			System.out.print(B[i][j] + " ");
		}
		System.out.print("\n");
	}
	
	System.out.println("Max Value:\t" + B[n][M]);
	
	System.out.println("Selected Packs: ");
	
	while (n != 0) {
		if (B[n][M] != B[n - 1][M]) {
			System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
			
			M = M - W[n-1];
		}
		
		n--;
	}
}
Fungsi knapsackDyProg() di Java

Fungsi knapsackDyProg() di Java

Penjelasan kode Knapsack:

  1. Buat tabel B[][]. Tetapkan nilai default untuk setiap sel adalah 0.
  2. Bangun tabel B[][] dengan cara bottom-up. Hitung tabel pilihan dengan rumus pengambilan.
  3. Hitung B[i][j]. Jika Anda tidak memilih paket i.
  4. Kemudian evaluasi: jika memilih paket i, akan lebih bermanfaat kemudian reset B[i][j].
  5. Telusuri tabel dari baris n ke baris 0.
  6. Jika Anda memilih paket n. Setelah memilih paket n, hanya dapat menambah bobot M – W[n – 1].


Dalam tutorial ini, Anda memiliki dua contoh. Berikut adalah kode java untuk menjalankan program di atas dengan dua contoh:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	//int W[] = new int[]{3, 4, 5, 9, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
	//int V[] = new int[]{3, 4, 4, 10, 4};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
	//int M = 11;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackDyProg(W, V, M, n);
}

Anda memiliki hasilnya:

  • Contoh Pertama:
0 0 0 3 3 3 3 3 3 3 3 3 
0 0 0 3 4 4 4 7 7 7 7 7 
0 0 0 3 4 4 4 7 7 8 8 8 
0 0 0 3 4 4 4 7 7 10 10 10 
0 0 0 3 4 4 4 7 8 10 10 11 
Max Value:	11
Selected Packs: 
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3
  • Contoh Kedua:
0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7 
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs: 
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Anda mungkin ingin: