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

Sırt Çantası Sorunu Nedir?

MKS Sırt Çantası Sorunu Bu, klasik bir kombinatoryal optimizasyon problemidir. Bir süpermarket n paketler (n ≤ 100). Paket i Ağırlığı W[i] ≤ 100 ve değeri V[i] ≤ 100 olan paketler var. Bir hırsız, taşıma kapasitesi M'yi (M ≤ 100) aşan ağırlık taşıyamaz. Hırsız, toplam değeri en üst düzeye çıkarmak için hangi paketleri almalıdı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ı:

• Kapasite dahilinde elde edilebilecek maksimum toplam değer.
• Hırsızın alması gereken paketlerin tam listesi.

Sırt çantası algoritması iki bilinen varyanta ayrılır:

• 0/1 Sırt Çantası Problemi Dinamik Programlama ile çözüldü. Her paket ya tamamen alınır ya da bırakılır; kesirli parçalar veya tekrarlar yoktur.
• Kesirli Sırt Çantası Problemi Açgözlü bir strateji ile çözüldü. Burada, kalan kapasiteyi doldurmak için herhangi bir paketin bir kısmını alabilirsiniz.

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

Böl ve yönet yöntemi, büyük bir problemi alt problemlere ayırır ve her alt problem kolaylaşana kadar bölmeye devam eder. Ancak, düz özyineleme genellikle aynı alt problemi birçok kez çözer ve iş gücünü boşa harcar.

Sırt Çantası Dinamik Programlamasının temel fikri, çözülen her alt problemi bir tabloda saklamaktır. Tekrarlama çağrıları, cevabı yeniden hesaplamak yerine okur ve böylece üstel bir özyinelemeyi polinom zamanlı koda dönüştürür.

Dinamik Programlamayı Kullanarak Sırt Çantası Sorununu Çözme

Dinamik Programlama çözümü tasarlamak için dört adımı izlersiniz:

• Önce en küçük alt problemleri çözün.
• Daha küçük çözümlerden yola çıkarak daha büyük bir alt probleme yönelik bir yineleme bağıntısı türetin.
• Alt problemlerin cevaplarını, yineleme bağıntısı kullanılarak aşağıdan yukarıya doğru hesaplanan bir tabloda saklayın.
• Tamamen doldurulmuş tablodan nihai cevabı oluşturun.

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

En uygun değer iki bağımsız faktöre bağlıdır:

1. Halen değerlendirme aşamasında olan kaç paket var?
2. Sırt çantasının hala taşıyabileceği kalan ağırlık.

Amaç fonksiyonu iki niceliğe bağlı olduğundan, seçenekler tablosu iki boyutlu olmalıdır. B[i][j] j ağırlık sınırı ile {1, …, i} paketleri arasından seçim yapıldığında elde edilebilecek maksimum değeri ifade eder.

• Son cevap B[n][M]Kapasite M altındaki tüm n paketler arasında en iyi toplam değer.
• Seçilen toplam ağırlık her zaman mevcut kapasiteyle sınırlıdır: B[i][j] ≤ j.

Örnek: Eğer B[4][10] = 8 ise, 10 kapasite altındaki ilk dört paketten elde edilebilecek en iyi toplam ağırlık 8'dir. Bu dört paketten bazıları atlanabilir.

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

• W[i], V[i] Burada i, {1, …, n} kümesindeki bir eleman olmak üzere, i. paketin ağırlığı ve değeridir.
• M Bu, sırt çantasının taşıyabileceği maksimum ağırlıktır.

Tek paketli temel durum: her kapasite j ≥ W[1] için:

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

Genel durum için, i paketini j kapasitesi altına dahil edip etmemeye karar verin:

• Eğer i paketi ise atlanan, B[i][j], kapasite j altında {1, …, i-1} paketlerini kullanan en iyi değere eşittir:

B[i][j] = B[i - 1][j]

• Eğer i paketi ise alınan (yalnızca W[i] ≤ j olduğunda izin verilir), B[i][j], V[i]'ye, kapasite j – W[i] altında {1, …, i-1} paketlerinden en iyi değerin eklenmesiyle elde edilir:

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

İki adaydan daha büyük olanını seçin.

Dinamik Programlamanın Temelleri

İki durumu birleştirerek tam tekrarlamayı elde ederiz:

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

Temel durum şudur: B[0][j] = 0 Her j için, çünkü sıfır paket, kapasiteden bağımsız olarak sıfır değer verir.

Seçenekler Tablosunu Hesaplayın

Tekrarlama bağıntısını kullanarak B'yi oluşturun. B doldurulduktan sonra, aynı tablo diğerini yönlendirir. tracSeçilen paketleri yeniden oluşturan e-geri bildirim. Tablo B'nin n + 1 satırı ve M + 1 sütunu vardır:

• 0. satır, sıfırlarla doldurulmuş temel durumdur.
• 0. satırı kullanarak 1. satırı, 1. satırı kullanarak 2. satırı hesaplayın ve n. satır tamamlanana kadar bu işleme devam edin.

Seçenekler Tablosu

Trace

B aşaması tamamlandıktan sonra, şunlara odaklanın: B[n][M]Kapasitesi M olan tüm n paket için en uygun toplam değer.

• If B[n][M] = B[n-1][M]n numaralı paket seçilmedi, bu nedenle devam edin. tracB[n-1][M]'den ing.
• If B[n][M] ≠ B[n-1][M]n numaralı paket seçildi, bu yüzden devam edin. tracB[n-1][M – W[n]]'den ing.

Tablonun 0. satırına ulaşana kadar tekrarlayın.

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

Not: ne zaman B[i][j] = B[i-1][j]Paket i seçilmedi. Değer B[n][M] Bu, sırt çantasına sığdırılan en uygun toplam değerdir.

İçin adımlar tracSeçilen paketlerin kullanımı:

• 1 Adım: i = n, j = M'den başlayın.
• 2 Adım: j sütununu aşağıdan yukarıya doğru tarayın ve B[i][j] > B[i-1][j] koşulunu sağlayan i satırını bulun. i paketini seçili olarak işaretleyin: Select[i] = true.
• 3 Adım: j = j – W[i] değerini güncelleyin. Eğer j > 0 ise 2. adıma dönün, aksi takdirde 4. adıma geçin.
• 4 Adım: Seçili olarak işaretlenmiş her paketi yazdırın.

Java Code

Aşağıdaki Java Bu yöntem B[][] dizisini aşağıdan yukarıya doğru doldurur, inceleme için tabloyu yazdırır ve ardından tracSeçilen paketler.

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: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Sırt çantasıDyProg() işlevi Java

Kodun açıklaması:

1. Tahsis tablosu B[][] ve her hücreyi 0'a sıfırlayın.
2. Önceki bölümdeki yineleme bağıntısını kullanarak B[][]'yi aşağıdan yukarıya doğru doldurun.
3. Her hücreyi “i paketini atla” değeriyle başlatın. B[i-1][j].
4. Eğer i paketini seçmek mümkünse ve kesinlikle daha iyi bir değer sağlıyorsa, hücreyi üzerine yazın.
5. TracSeçilen öğeleri n. satırdan 0. satıra geri taşı.
6. n numaralı paket seçildiğinde, kalan kapasiteyi azaltın. W[n-1].

Düzeltme notu: orijinal kod parçacığı değiştirilmiş parametre M okumaya devam ederken B[n][M]Yukarıdaki daha güvenli sürüm ayrı bir imleç kullanır. j için trace.

MKS Java Sürücü algoritmayı iki örnek üzerinde çalıştırır:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Birinci örneğin çıktısı:

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 örneğin çıktısı:

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

0/1 Sırt Çantasının Zaman ve Mekan Karmaşıklığı

• Zaman karmaşıklığı: O(n · M) — iç içe geçmiş iki döngü, n öğeyi M+1 kapasite durumunda tarar.
• Alan karmaşıklığı: Tablonun tamamı için O(n · M), kee ile O(M)'ye indirgenebilir.ping yalnızca önceki satır tracElektronik iadeye gerek yoktur.

çalışma zamanı sözde-polinom: M değerine göre polinom, ancak M'yi kodlamak için kullanılan bitlere göre üsteldir. Bu nedenle, Dinamik Programlama pratikte verimli olsa bile, 0/1 Sırt Çantası problemi NP-zor olmaya devam etmektedir.

0/1 Sırt Çantası Probleminin Uygulamaları

• Ağırlık sınırları dahilinde kargo yükleme, konteyner paketleme ve depoda ürün toplama.
• Sabit maliyetli ve beklenen getirili yatırım projeleri arasında bütçe dağılımı.
• Üretimde, tek tek parçaları ayırmayı imkansız hale getiren kesim sorunları.
• Merkle-Hellman gibi, sırt çantası zorluğu prensibine dayanan şifreleme yöntemleri.
• Bulut bilişimde kaynak kısıtlı zamanlama ve CPU görev yerleşimi.
• Sabit özellik bütçesi altında makine öğreniminde özellik seçimi.

SSS