Skip to content
7 Februari 2010 / Jeffrey Hermanto Halimsetiawan

Unbounded Knapsack Problem dalam Bahasa Java


Penjelasan Problem :

Seorang pendaki harus membawa 3 barang yaitu : makanan, obat-obatan dan baju. Makanan memiliki nilai 4, obat-obatan 3, dan baju 5 (baju memiliki nilai paling tinggi, dst). Untuk membawa barang-barang tersebut, sang pendaki menggunakan sebuah back pack dengan kapasitas 3 liter. Satu unit makanan memiliki ukuran 1 liter. Satu unit obat-obatan berukuran 1/4 liter. Dan satu unit baju berukuran 1/2 liter.

  1. Justifikasi algoritma apakah yang bisa memaksimalkan nilai dari barang yang dibawa oleh pendaki. Jelaskan alasannya!
  2. Buatlah algoritmanya!
  3. Analysis running time dari algoritma yang anda kembangkan!
  4. Implementasikan algoritma tersebut!

Penjelasan Algoritma
Dalam kasus di atas, diperlukan sebuah algoritma yang digunakan untuk mencari nilai yang optimum dari barang yang dibawa oleh pendaki dengan batas beban backpack pendaki. Agar didapatkan nilai yang optimal maka digunakan algoritma unbounded-knapsack untuk memecahkan permasalah di atas dengan pendekatan secara Dynamic Programming (DP). Algoritma unbounded knapsack atau yang disebut juga dengan integer-knapsack merupakan pengembangan dari algoritma knapsack dimana tidak ada batasan pengambilan jumlah sebuah item tetapi tetap memperhatikan batasan beban (weight). Karena seorang pendaki harus membawa minimal 1 untuk semua item barang, maka ada sedikit modifikasi algoritma unbounded knapsack yaitu setelah masing-masing diambil satu barang, baru dilakukan dynamic programming untuk mencari nilai yang maksimal dengan weight yang sudah dikurangi tersebut. Alasan menggunakan pendekatan secara dynamic programming karena greedy pada permasalahan knapsack di atas tidak ditemukan adanya greedy choice sehingga ada beberapa kasus dimana solusi greedy tidak optimal. Contoh kasusnya adalah sebagai berikut :

MAKSIMUM WEIGHT = 3

ITEM WEIGHT VALUE RATIO ( VALUE / WEIGHT)
Obat 0.25 3 12
Baju 0.4 4 10
Makanan 0.95 4 4.2

Weight setelah dikurangi semua item

= 3 – 0.25 – 0.95 – 0.4

= 1.4

Pendekatan :

  1. Greedy :  W = 0.25 * 5 = 1.25 || V = 3 * 5 = 15
  2. DP :           W = 0.25 * 4 + 0.4 * 1 = 1.4 || V   = 3 * 4 + 4 * 1 = 1

Dari contoh kasus di atas, Greedy menghasilkan value 15 sedangkan DP menghasilkan value 16 sehingga terbukti bahwa greedy tidak menghasilkan solusi yang optimal seperti pada dynamic programming.

Psudocode

    Algoritma Knapsack(weight,best[],weights[],values[],n)
    {
      i, space, m, t, itemKnown[];

      for m from 1 to weight
         for i from 0 to n
         {
            if ((space = m-weights[i]) >= 0)
            {
               t = best[space] + values[i];
               if (t >= best[m])
               {
                  best[m]  = t;
                  itemKnown[m] = i;
               }
            }
         }
      for (m=weight; m>0 ; m-=weights[itemKnown[m]] )
         solution[itemKnown[m]]++;
      return best[c];
    }

Implementasi

    int unboundedKnapsack(int c, int n, int[] weights, int[] values, int[] solution )
    {

        int i, space, m, t,
            best[], bestItem[];

            bestItem = new int [c+1];
            best  = new int [c+1];
            Arrays.fill(best, 0);

            for ( m = 1; m <= c; m++ )
                for (i = 0; i < n; i++) {                     if ( (space = m-weights[i]) >= 0 )
                    {
                        t = best[space] + values[i];
                        if ( t >= best[m] )
                        {
                            best[m]  = t;
                            bestItem[m] = i;
                        }
                    }
                for (int iterator : best){
                    areaOutput.append(iterator + " ");
                }
                areaOutput.append("\n");
             }

            for (m=c; m>0 ; m-=weights[bestItem[m]] )
             solution[bestItem[m]]++;

            return best[c];
    }

Untuk lebih lengkapnya, silahkan download : Unbounded Knapsack Problem dalam Bahasa Java – Jeffrey Hermanto

  1. bOOn / Okt 29 2010 14:12

    keep posting guys….

  2. shukiby / Mei 31 2012 17:05

    mantap….gan !!!
    ijin copy ya….

    • Jeffrey Hermanto Halimsetiawan / Jul 2 2012 21:00

      silahkan, semoga bermanfaat🙂

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: