0/1 Perbaikan Masalah Knapsack menggunakan Contoh Pemrograman Dinamis

Apa Masalah Ransel itu?

The Masalah Ransel adalah masalah optimasi kombinatorial klasik. Sebuah supermarket menyimpan n paket (n ≤ 100). Paket i memiliki berat W[i] ≤ 100 dan nilai V[i] ≤ 100. Seorang pencuri tidak dapat membawa berat yang melebihi kapasitas M (M ≤ 100). Paket mana yang harus diambil pencuri untuk memaksimalkan nilai total?

Memasukkan:

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

Keluaran:

• Nilai total maksimum yang dapat diperoleh dalam kapasitas tersebut.
• Isi paket persis yang harus diambil pencuri.

Algoritma Knapsack terbagi menjadi dua varian yang terkenal:

• Masalah Ransel 0/1 Diselesaikan dengan Pemrograman Dinamis. Setiap paket diambil secara utuh atau ditinggalkan — tidak ada bagian pecahan dan tidak ada duplikat.
• Masalah Knapsack Pecahan Diselesaikan dengan Strategi Serakah. Di sini Anda dapat mengambil sebagian kecil dari paket apa pun untuk mengisi kapasitas yang tersisa.

Cara Menyelesaikan Masalah Knapsack Menggunakan Pemrograman Dinamis disertai Contoh

Metode bagi-dan-taklukkan membagi masalah besar menjadi submasalah, lalu terus membagi hingga setiap submasalah menjadi mudah. ​​Namun, rekursi biasa sering kali menyelesaikan submasalah yang sama berkali-kali dan membuang-buang tenaga.

Ide inti dari Knapsack Dynamic Programming adalah menyimpan setiap submasalah yang telah dipecahkan dalam sebuah tabel. Panggilan berulang membaca jawabannya alih-alih menghitung ulang, mengubah rekursi eksponensial menjadi kode waktu polinomial.

Selesaikan Masalah Knapsack menggunakan Pemrograman Dinamis

Untuk mendesain solusi Pemrograman Dinamis, Anda mengikuti empat langkah:

• Selesaikan submasalah terkecil terlebih dahulu.
• Turunkan suatu persamaan rekursi yang membangun jawaban submasalah dari submasalah yang lebih kecil.
• Simpan jawaban submasalah dalam tabel yang dihitung dari bawah ke atas menggunakan relasi rekursif.
• Susun jawaban akhir dari tabel yang sudah terisi penuh.

Analisis Masalah Knapsack 0/1

Nilai optimal bergantung pada dua faktor independen:

1. Berapa banyak paket yang masih dalam pertimbangan?
2. Berat sisa yang masih bisa ditampung oleh ransel.

Karena fungsi objektif bergantung pada dua besaran, tabel opsi harus dua dimensi. Misalkan B[i][j] menunjukkan nilai maksimum ketika memilih di antara paket {1, …, i} dengan batas berat j.

• Jawaban akhirnya adalah B[n][M], nilai total terbaik di seluruh n paket di bawah kapasitas M.
• Berat total yang dipilih selalu dibatasi oleh kapasitas saat ini: B[i][j] ≤ j.

Contoh: jika B[4][10] = 8, berat total terbaik dari empat paket pertama di bawah kapasitas 10 adalah 8. Beberapa dari empat paket tersebut dapat dilewati.

Rumus Menghitung B[i][j]

• W[i], V[i] adalah berat dan nilai paket i, di mana i berada dalam {1, …, n}.
• M adalah berat maksimum yang dapat dibawa oleh ransel tersebut.

Kasus dasar dengan satu paket: untuk setiap kapasitas j ≥ W[1]:

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

Untuk kasus umum, putuskan apakah akan memasukkan paket i di bawah kapasitas j:

• Jika paket i adalah dilewati, B[i][j] sama dengan nilai terbaik menggunakan paket {1, …, i-1} di bawah kapasitas j:

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

• Jika paket i adalah diambil (diperbolehkan hanya jika W[i] ≤ j), B[i][j] sama dengan V[i] ditambah nilai terbaik dari paket {1, …, i-1} di bawah kapasitas j – W[i]:

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

Pilih yang lebih besar dari kedua kandidat tersebut.

Dasar Pemrograman Dinamis

Menggabungkan kedua kasus tersebut menghasilkan kekambuhan lengkap:

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

Kasus dasarnya adalah B[0][j] = 0 untuk setiap j, karena nol paket memberikan nilai nol terlepas dari kapasitasnya.

Hitung Tabel Pilihan

Bangun B menggunakan rekursi. Setelah B terisi, tabel yang sama akan menggerakkan yang berikutnya. trace-back yang merekonstruksi paket yang dipilih. Tabel B memiliki n + 1 baris dan M + 1 kolom:

• Baris 0 adalah kasus dasar, diisi dengan angka nol.
• Gunakan baris 0 untuk menghitung baris 1, baris 1 untuk menghitung baris 2, dan lanjutkan hingga baris n selesai.

Tabel Pilihan

Trace

Setelah B selesai, fokuslah pada B[n][M], nilai total optimal di seluruh n paket dengan kapasitas M.

• If B[n][M] = B[n-1][M]Paket n tidak dipilih, jadi lanjutkan. tracing dari B[n-1][M].
• If B[n][M] ≠ B[n-1][M]Paket n telah dipilih, jadi lanjutkan. tracing dari B[n-1][M – W[n]].

Ulangi langkah ini hingga mencapai baris 0 pada tabel.

Algoritma untuk Mencari Tabel Pilihan untuk Menemukan Paket Terpilih

Catatan: kapan pun B[i][j] = B[i-1][j], paket i tidak dipilih. Nilainya B[n][M] adalah nilai total optimal yang dikemas ke dalam ransel.

Langkah-langkah untuk tracdengan paket yang dipilih:

• Langkah 1: Mulai dari i = n, j = M.
• Langkah 2: Pindai kolom j dari bawah ke atas hingga Anda menemukan baris i di mana B[i][j] > B[i-1][j]. Tandai paket i sebagai terpilih: Select[i] = true.
• Langkah 3: Perbarui j = j – W[i]. Jika j > 0, kembali ke Langkah 2, jika tidak, lanjutkan ke Langkah 4.
• Langkah 4: Cetak setiap paket yang ditandai sebagai terpilih.

Java Code

Berikut ini Java Metode ini mengisi B[][] dari bawah ke atas, mencetak tabel untuk diperiksa, dan kemudian tracpaket yang dipilih.

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

Fungsi knapsackDyProg() di Java

Penjelasan kodenya:

1. Tabel alokasi B[][] dan menginisialisasi setiap sel ke 0.
2. Isi B[][] dari bawah ke atas menggunakan rekursi dari bagian sebelumnya.
3. Awali setiap sel dengan nilai “skip package i” B[i-1][j].
4. Jika memilih paket i memungkinkan dan memberikan nilai yang jauh lebih baik, timpa sel tersebut.
5. Trace. Pilih item yang dipilih dari baris n kembali ke baris 0.
6. Setiap kali paket n dipilih, kurangi kapasitas yang tersisa sebesar W[n-1].

Catatan perbaikan: cuplikan asli yang bermutasi parameter M sambil tetap membaca B[n][M]Versi yang lebih aman di atas menggunakan kursor terpisah. j untuk trace.

The Java Driver menjalankan algoritma pada dua contoh yang telah dikerjakan:

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

Output untuk 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

Output untuk 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

Kompleksitas Waktu dan Ruang dari Knapsack 0/1

• Kompleksitas waktu: O(n · M) — kedua loop bersarang tersebut menyapu n item melalui M+1 status kapasitas.
• Kompleksitas ruang: O(n · M) untuk tabel lengkap, dapat direduksi menjadi O(M) dengan keeping hanya baris sebelumnya ketika tracBalasan email tidak diperlukan.

Waktu eksekusinya adalah pseudo-polinomial: polinomial dalam nilai M tetapi eksponensial dalam bit yang digunakan untuk mengkodekan M. Itulah mengapa masalah 0/1 Knapsack tetap NP-hard meskipun Pemrograman Dinamis efisien dalam praktiknya.

Penerapan Masalah Knapsack 0/1

• Pemuatan kargo, pengemasan kontainer, dan pengambilan barang di gudang dengan batasan berat.
• Alokasi anggaran di seluruh proyek investasi dengan biaya tetap dan pengembalian yang diharapkan.
• Masalah pemotongan bahan baku dalam proses manufaktur yang tidak dapat dipisahkan menjadi bagian-bagian individual.
• Skema kriptografi seperti Merkle-Hellman yang dibangun berdasarkan ketahanan terhadap serangan knapsack.
• Penjadwalan dengan keterbatasan sumber daya dalam komputasi awan dan penempatan tugas CPU.
• Pemilihan fitur dalam pembelajaran mesin dengan anggaran fitur tetap.

Pertanyaan Umum Demo Slot