Implementasi Masalah Knapsack di Jawa

1. Perkenalan

Masalah knapsack adalah masalah optimasi kombinatorial yang memiliki banyak aplikasi. Dalam tutorial ini, kami akan menyelesaikan masalah ini di Java.

2. Masalah Knapsack

Dalam masalah ransel, kami memiliki satu set item. Setiap item memiliki bobot dan nilai yang berharga:

Kami ingin memasukkan barang-barang ini ke dalam ransel. Namun, ada batasan berat:

Oleh karena itu, kita perlu memilih item yang berat totalnya tidak melebihi batas berat, dan nilai totalnya setinggi mungkin. Misalnya, solusi terbaik untuk contoh di atas adalah memilih item 5kg dan item 6kg, yang memberikan nilai maksimum $ 40 dalam batas berat.

Masalah ransel memiliki beberapa variasi. Dalam tutorial ini, kami akan fokus pada masalah ransel 0-1. Pada soal knapsack 0-1, setiap item harus dipilih atau ditinggalkan. Kami tidak dapat mengambil sebagian dari satu item. Selain itu, kami tidak dapat mengambil item beberapa kali.

3. Definisi Matematis

Sekarang mari kita memformalkan masalah ransel 0-1 dalam notasi matematika. Diberikan satu set item n dan batas bobot W , kita dapat mendefinisikan masalah optimasi sebagai:

Masalah ini NP-hard. Oleh karena itu, tidak ada algoritma waktu-polinomial untuk menyelesaikannya saat ini. Namun, ada algoritma waktu polinomial semu menggunakan pemrograman dinamis untuk masalah ini.

4. Solusi Rekursif

Kita dapat menggunakan rumus rekursi untuk menyelesaikan masalah ini:

Dalam rumus ini, M (n, w) adalah solusi optimal untuk n item dengan batas bobot w . Ini adalah maksimum dari dua nilai berikut:

  • Solusi optimal dari (n-1) item dengan batas berat w (tidak termasuk item ke- n )
  • Nilai item ke- n ditambah solusi optimal dari (n-1) item dan w dikurangi bobot item ke- n (termasuk item ke- n )

Jika berat item ke- n lebih dari batas berat saat ini, kami tidak memasukkannya. Oleh karena itu, ini termasuk dalam kategori pertama dari dua kasus di atas.

Kami dapat menerapkan rumus rekursi ini di Jawa:

int knapsackRec(int[] w, int[] v, int n, int W) { if (n  W) { return knapsackRec(w, v, n - 1, W); } else { return Math.max(knapsackRec(w, v, n - 1, W), v[n - 1] + knapsackRec(w, v, n - 1, W - w[n - 1])); } } 

Dalam setiap langkah rekursi, kita perlu mengevaluasi dua solusi sub-optimal. Oleh karena itu, waktu berjalan dari solusi rekursif ini adalah O (2n).

5. Solusi Pemrograman Dinamis

Pemrograman dinamis adalah strategi untuk membuat linierisasi masalah pemrograman yang sulit secara eksponensial. Idenya adalah untuk menyimpan hasil subproblem sehingga kita tidak perlu menghitung ulang nanti.

Kami juga dapat menyelesaikan masalah knapsack 0-1 dengan pemrograman dinamis. Untuk menggunakan pemrograman dinamis, pertama kita membuat tabel 2-dimensi dengan dimensi dari 0 sampai n dan 0 W . Kemudian, kami menggunakan pendekatan bottom-up untuk menghitung solusi optimal dengan tabel ini:

int knapsackDP(int[] w, int[] v, int n, int W) { if (n <= 0 || W <= 0) { return 0; } int[][] m = new int[n + 1][W + 1]; for (int j = 0; j <= W; j++) { m[0][j] = 0; } for (int i = 1; i <= n; i++) { for (int j = 1; j  j) { m[i][j] = m[i - 1][j]; } else { m[i][j] = Math.max( m[i - 1][j], m[i - 1][j - w[i - 1]] + v[i - 1]); } } } return m[n][W]; } 

Dalam solusi ini, kami memiliki loop bersarang di atas nomor item n dan batas berat W . Oleh karena itu, waktu berjalannya adalah O (nW) .

6. Kesimpulan

Dalam tutorial ini, kami menunjukkan definisi matematika dari soal ransel 0-1. Kemudian kami memberikan solusi rekursif untuk masalah ini dengan implementasi Java. Akhirnya, kami menggunakan pemrograman dinamis untuk mengatasi masalah ini.

Seperti biasa, kode sumber artikel tersedia di GitHub.