0/1 Dinamik Programlama Örneği Kullanarak Sırt Çantası Sorununu Düzeltme

Sırt Çantası Sorunu Nedir?

Sırt Çantası Sorunu Algoritma kombinatorikte çok yararlı bir problemdir. Süpermarkette n adet paket var (n ≤ 100) i paketinin ağırlığı W[i] ≤ 100 ve değeri V[i] ≤ 100. Bir hırsız süpermarkete girer, hırsız M'yi aşan ağırlık taşıyamaz (M ≤ 100) ). Burada çözülmesi gereken sorun şudur: Hırsız en yüksek değeri elde etmek için hangi paketleri alacaktır?

Giriş:

Maksimum ağırlık M ve paket sayısı n.
Ağırlık dizisi W[i] ve karşılık gelen değer V[i].

Çıktı:

Kapasitedeki değeri ve karşılık gelen ağırlığı maksimuma çıkarın.
Hırsızın hangi paketleri götüreceği.

Sırt çantası algoritması ayrıca iki türe ayrılabilir:

Dinamik programlamayı kullanan 0/1 Sırt Çantası problemi. Bu Sırt Çantası algoritma türünde her paket alınabilir veya alınmayabilir. Ayrıca hırsız, alınan bir paketin küçücük bir miktarını veya bir paketi birden fazla alamaz. Bu tip Dinamik Programlama Yaklaşımı ile çözülebilir.
Kesirli Sırt Çantası problem algoritması. Bu tür Açgözlü Strateji ile çözülebilir.

Örnekle Dinamik Programlama Kullanılarak Sırt Çantası Sorunu Nasıl Çözülür

Böl-yönet stratejisinde çözülmesi gereken problemi alt problemlere bölersiniz. Alt problemler daha küçük alt problemlere bölünür. Bu görev, kolayca çözülebilecek alt problemler elde edene kadar devam edecektir. Ancak bu tür bir bölünme sürecinde aynı sorunla birçok kez karşılaşabilirsiniz.

Knapsack dinamik programlamanın temel fikri, çözülmüş alt problemlerin çözümlerini saklamak için bir tablo kullanmaktır. Tekrar bir alt problemle karşılaşırsanız tekrar çözmeye gerek kalmadan tablodaki çözümü almanız yeterli. Bu nedenle dinamik programlamayla tasarlanan algoritmalar oldukça etkilidir.

Bir problemi dinamik programlama ile çözmek için aşağıdaki görevleri yapmanız gerekir:

En küçük alt problemlerin çözümlerini bulun.
En küçük alt problemlerin bile çözümlerini kullanarak bir alt problem çözümü oluşturmak için formülü (veya kuralı) bulun.
Alt problemlerin çözümlerini saklayan bir tablo oluşturun. Daha sonra bulunan formüle göre alt problemin çözümünü hesaplayın ve tabloya kaydedin.
Çözülmüş alt problemlerden asıl problemin çözümünü bulursunuz.

0/1 Sırt Çantası Problemini Analiz Edin

Dinamik programlamayı kullanarak 0/1 Sırt Çantası problemini analiz ederken dikkat çeken bazı noktalar bulabilirsiniz. Sırt çantası algoritmasının değeri iki faktöre bağlıdır:

Kaç paket değerlendiriliyor
Sırt çantasının depolayabileceği kalan ağırlık.

Bu nedenle iki değişken miktarınız var.

Dinamik programlamayla yararlı bilgilere sahip olursunuz:

amaç fonksiyonu iki değişken miktara bağlı olacaktır
seçenekler tablosu 2 boyutlu bir tablo olacaktır.

B[i][j]'yi çağırmak, j ağırlık limiti ile {1, 2, …, i} paketlerinde seçilerek mümkün olan maksimum değerse.

Ağırlık limiti M olan n pakette seçildiğinde maksimum değer B[n][M] olur. Başka bir deyişle: Seçilecek i paketleri olduğunda, sırt çantasının maksimum ağırlığı j olduğunda B[i][j] en uygun ağırlıktır.
Optimum ağırlık her zaman maksimum ağırlıktan küçük veya ona eşittir: B[i][j] ≤ j.

Örneğin: B[4][10] = 8. Bu, en uygun durumda, seçilebilecek 8 ilk paket olduğunda (4. ila 1. paket) ve maksimum ağırlığın seçilen paketlerin toplam ağırlığının 4 olduğu anlamına gelir. sırt çantası sayısı 10'dur. 4 öğenin tamamının seçilmesi gerekli değildir.

B[i][j]'yi Hesaplayacak Formül

Giriş yaparken şunları tanımlarsınız:

W[i], V[i] ise i paketinin ağırlığı ve değeridir; {1, …, n}.
M, sırt çantasının taşıyabileceği maksimum ağırlıktır.

Sadece 1 paketin seçilebilmesi durumunda. Her j için B[1][j]'yi hesaplarsınız: bu, sırt çantasının maksimum ağırlığı ≥ 1. paketin ağırlığı anlamına gelir

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

Ağırlık limiti j ile, {1, 2, …, i – 1, i} paketleri arasında en büyük değere sahip olacak optimal seçimler iki olasılığa sahip olacaktır:

Eğer i paketi seçilmezse, B[i][j] ağırlık limiti j olan {1, 2, …, i – 1} paketleri arasından seçilerek mümkün olan maksimum değerdir. Var:

B[i][j] = B[i – 1][j]

Eğer i paketi seçilirse (tabii ki bu durumu sadece W[i] ≤ j olduğunda düşünün), o zaman B[i][j], i paketinin V[i] değerine eşittir artı maksimum değer, aşağıdakiler arasından seçim yapılarak elde edilebilir: ağırlık limitli (j – W[i]) paketler {1, 2, …, i – 1}. Yani sahip olduğunuz değer açısından:

B[i][j] = V[i] + B[i – 1][j – W[i]]

Mümkün olan maksimum değer olan B[i][j]'nin yaratılmasından dolayı, B[i][j] yukarıdaki 2 değerin maksimumu olacaktır.

Dinamik Programlamanın Temelleri

Bu nedenle i paketini seçmenin daha iyi olup olmadığını düşünmelisiniz. Oradan aşağıdaki gibi özyinelemeli formüle sahip olursunuz:

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

0 paket = 0 arasından seçim yaparak B[0][j] = mümkün olan maksimum değeri görmek kolaydır.

Seçenekler Tablosunu Hesaplayın

Yukarıdaki özyinelemeli formüle dayalı olarak bir seçenekler tablosu oluşturursunuz. Sonuçların doğru olup olmadığını kontrol etmek için (tam olarak değilse, B[i][j] amaç fonksiyonunu yeniden oluşturursunuz). B[i][j] amaç fonksiyonunun ve seçenekler tablosunun oluşturulması yoluyla izlemeyi yönlendireceksiniz.

B seçenekleri tablosu n + 1 satır, M + 1 sütun içerir,

Öncelikle dinamik programlamanın temelleri ile dolu: Satır 0'da tamamı sıfırlar bulunur.
Özyinelemeli formüller kullanarak, 0. satırı hesaplamak için 1. satırı kullanın, 1. satırı hesaplamak için 2. satırı kullanın, vb.… tüm satırlar hesaplanana kadar.

Seçenekler Tablosunu Hesaplayın — Seçenekler Tablosu

Iz

Seçenekler tablosunu hesaplarken, ağırlık limiti M olan tüm n pakette seçim yaparken elde edilen maksimum değer olan B[n][M] ile ilgileniyorsunuz.

If B[n][M] = B[n – 1][M] o zaman n paketi seçilmezse, B[n – 1][M]'yi izlersiniz.
If B[n][M] ≠ B[n – 1][M], en uygun seçimin n paketine ve B[n – 1][M – W[n]] izine sahip olduğunu fark edersiniz.

Seçenekler tablosunun 0. satırına ulaşana kadar izlemeye devam edin.

Seçilen Paketleri Bulmak İçin Seçenekler Tablosunu Arama Algoritması

Not: B[i][j] = B[i – 1][j] ise i paketi seçilmez. B[n][W] sırt çantasına konulan paketin optimal toplam değeridir.

İzleme adımları:

1. Adım: i = n'den başlayarak, j = M.
2. Adım: j sütununa aşağıdan yukarıya doğru baktığınızda, B[i][j] > B[i – 1][j] olacak şekilde i doğrusunu bulursunuz. Seçilen paketi işaretle i: [i] = doğru;
3. Adım: j = B[i][j] – W[i]. Eğer j > 0 ise, 2. adıma geçin, aksi takdirde 4. adıma geçin
4. Adım: Seçilen paketleri yazdırma seçenekleri tablosuna göre.

Java Kod

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--;
	}
}

Sırt Çantası kodunun açıklaması:

B tablosunu oluştur[][]. Her hücre için varsayılan değeri 0 olarak ayarlayın.
B tablosunu[][] aşağıdan yukarıya doğru oluşturun. Geri alma formülüyle seçenekler tablosunu hesaplayın.
B[i][j]'yi hesaplayın. i paketini seçmezseniz.
O zaman değerlendirin: i paketini seçerseniz, B[i][j]'yi sıfırlamaktan daha faydalı olacaktır.
Tabloyu n. satırdan 0. satıra kadar izleyin.
Paket n'yi seçerseniz. n paketini seçtikten sonra yalnızca M – W[n – 1] ağırlığını ekleyebilirsiniz.

Bu eğitimde iki örneğiniz var. Yukarıdaki programı iki örnekle çalıştırmak için Java kodu:

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);
}

Çıktıya sahipsiniz:

İlk Örnek:

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

İkinci Örnek:

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

Beğenebilirsin: