PENERAPAN ALGORITMA GREEDY PADA PERMASALAHAN KNAPSACK UNTUK OPTIMASI PENGANGKUTAN PETI KEMAS

PENERAPAN ALGORITMA GREEDY PADA PERMASALAHAN  KNAPSACK UNTUK OPTIMASI PENGANGKUTAN PETI KEMAS    2)  Agus Ambarwari​ , Nur Witdi Yanto​ Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam  Institut Pertanian Bogor (IPB)  Jl. Meranti Kampus IPB Darmaga­Bogor Telp/Fax : (0251) 625584  1)​ 2)​ E­mail: ​ [email protected]​ , ​ nur_004@​ apps.ipb.ac.id      Abstrak  Optimasi  merupakan  metode  pemecahan  masalah  maksimalisasi  atau  minimalisasi.  Optimasi  sangat  bermanfaat  untuk  meningkatkan  produktivitas kerja. Terutama pada bidang  (jasa)  pengangkutan  barang  (seperti  pengangkutan  peti  kemas  dalam  sebuah  kapal).  Dalam  usaha  tersebut,  diinginkan  suatu  keuntungan  yang  maksimal  untuk   mengangkut barang  yang  ada  dengan  tidak  melebihi  batas  kapasitas  yang   ada.  Permasalahan semacam ini  sering  dianalogikan  dengan  menggunakan  permasalahan  Knapsack.  Solusi  dari  permasalahan  Knapsack  pada  pengangkutan  peti  kemas,  dapat  dilakukan  dengan  menerapkan  algoritma  Greedy.  Algoritma  Greedy  yang  diterapkan  ke  dalam  suatu  sistem  dapat  digunakan  untuk  menyelesaikan  permasalahan  Knapsack  pada  pengangkutan  peti  kemas dengan perolehan keuntungan lebih besar.  1)​

Keyword:​  Algoritma Greedy, Knapsack Problem, Optimasi, Peti Kemas.    1.

PENDAHULUAN  Semakin  maju  dan  berkembangnya  teknologi,  dibutuhkan  juga  kinerja  yang  cepat,   tepat,  dan  efisien.  Dengan  pemanfaatan  teknologi  yang  sudah  dikembangkan,  diharapkan  produktivitas  suatu  perusahaan  semakin  meningkat.  Salah  satu  contoh  perusahaan  yang  sangat  dibutuhkan  dalam  perdagangan adalah perusahaan pengiriman peti kemas. Perusahaan  peti  kemas  melakukan  pengiriman  barang  antar  pulau  maupun  negara, dengan menggunakan  alat  transportasi  kapal,  truk,  atau  kereta  api.  Bukan  sekedar  pengangkutan  saja  yang  harus  dipikirkan,  melainkan  juga  harus  dipikirkan  efisiensi  dan  keuntungan  yang  dapat  diperoleh.  Dengan  pertimbangan  tersebut,  diharapkan  dapat  diperoleh  keuntungan  yang  besar.  Pengiriman  barang  menggunakan  peti  kemas  ini  tidak  hanya  terjadi  sekali  saja,  tetapi  dapat  berulang  kali.  Oleh  karena  itu,  dibutuhkan  suatu  sistem  yang  dapat  membantu  petugas  di  lapangan  dalam  seleksi  peti  kemas  di  pelabuhan.  Dengan  syarat  berat  muatan  peti  kemas  tidak  melebihi  kapasitas  kapal  pengangkut,  dan  masing­masing  peti kemas tersebut memiliki  nilai yang tinggi.  Dari  permasalahan  tersebut,  munculah  suatu  permasalahan  yang  dikenal  dengan  istilah  “Permasalahan Knapsack” atau lebih dikenal “​ Knapsack Problem​ ”. Masalah Knapsack  merupakan  suatu  permasalahan  bagaimana  memilih  objek  dari  sekian  banyak  dan  berapa  besar  objek  tersebut  akan  disimpan,  sehingga  diperoleh  suatu  penyimpanan  yang  optimal 

dengan  memperhatikan  objek  yang  terdiri  dari  n  objek  (1,  2,  3,  …,  n).  Dimana  setiap   objek  memiliki  bobot  (​ Wi​ )  dan  profit  (​ Pi​ ),  dengan  memperhatikan  juga  kapasitas  dari  media  penyimpanan sebesar ​ M​  dan nilai probabilitas dari setiap objek (​ Xi​ ) (Prihandono, 2009).  Sehingga  untuk  menyelesaikan  permasalahan  tersebut  diperlukan  suatu  algoritma  yang  dapat  menghasilkan  solusi  yang  optimal,  efektif,  dan  efisien. Salah satu algoritma yang  sesuai  dalam  hal  optimasi  pengangkutan  peti  kemas  adalah  dengan  menggunakan  algoritma  Greedy.  Metode  Greedy  merupakan  salah  satu  cara  untuk mendapatkan solusi  optimal dalam  proses penyimpanan.  Berdasarkan  hal   tersebut,  dalam  tulisan  ini  akan  diterapkan  suatu  sistem  komputer   yang  bertujuan  untuk  mempercepat  proses  pemilihan  peti  kemas  dengan  menggunakan  algoritma  Greedy.  Sehingga  dapat  memberikan  solusi  optimal  dalam  melakukan  pemilihan  peti  kemas  yang  akan  dimasukkan  ke  dalam  kapal  pengangkut  dan  keuntungan  yang  diperoleh maksimal.    2. TINJAUAN PUSTAKA  2.1. Peti Kemas  Peti  kemas  (​ container​ )  merupakan  gudang  kecil  yang  berjalan  untuk  mengangkut  barang  dari  satu  tempat  ke tempat lain, harus bersama­sama  dengan alat pengangkutnya yaitu  kapal  angkut  kontainer,  truk,  atau  kereta  api  sampai  ke  tempat  yang  dituju.  Hal  inilah  yang  menyebabkan  peralihan  angkutan  barang  umum  menjadi  angkutan  barang  dengan  menggunakan  kontainer  yang menonjol dalam beberapa dekade terakhir. Hal ini juga terlihat  pada  pelabuhan­pelabuhan  kecil  yang  sudah  menunjukkan  trend  peralihan  ke  kontainer,  karena  alasan  ekonomi  yang  berkaitan  dengan  kecepatan  bongkar  muat  dan biaya yang lebih  rendah.  Pergerakan  kontainer  dari  satu  tempat  ke  tempat  lain  tanpa  adanya  pembatasan  teritorial/wilayah  pembawa  muatan  di  dalamnya  (​ cargo​ )  secara  aman  dan  efisien  dapat  dipindah­pindahkan.  Oleh  karena  itu  kontainer  harus  laik  laut  (​ sea  worthy​ ) mampu menahan  getaran  pada  waktu  pengangkutan  di  laut  maupun  di  darat.  Dan  tahan  terhadap  iklim  dan  suhu  yang  berbeda­beda  (Indrianingsih,  (Online)).  Bentuk  kontainer  ada   yang  mempunyai  standar Internasional, bentuknya dapat disesuaikan dengan kebutuhan pemakai, yaitu:  1) Untuk keperluan militer (​ army container​ )  2) Untuk logistik (​ oil offshore​ )  3) Untuk ​ office ​ dan logistik bangunan (​ building and road project contractor​ )  Pada  kontainer  mempunyai  ​ fiting  ​ sudut   dan  kunci  putar,  sehingga  antara  satu  kontainer  dengan  kontainer  lainnya  dapat  disatukan atau dilepaskan. Pada tempat pengiriman  barang  dalam satuan  yang lebih kecil, barang­barang tersebut dimasukkan ke dalam kontainer  kemudian dikunci atau disegel untuk siap dikirimkan.    2.2. Permasalahan Knapsack (​ Knapsack Problem​ )  Knapsack  ​ adalah  tas  atau  karung  yang  digunakan untuk memasukkan sesuatu barang,  namun tidak semua barang dapat ditampung ke dalam karung tersebut. Karung tersebut hanya 

dapat  menyimpan  beberapa  objek  dengan  total  ukurannya  (​ weight​ )  lebih  kecil  atau  sama  dengan ukuran kapasitas karung (Wahab, 2008).  Knapsack  problem  ​ merupakan   masalah  di  mana  orang  dihadapkan  pada  persoalan  optimasi  dalam  pemilihan  benda  yang  dapat  dimasukkan  ke  dalam  sebuah  wadah  yang  memiliki  keterbatasan  ruang  atau  daya  tampung.  Dengan  adanya  optimasi  dalam  pemilihan  benda  yang  akan   dimasukkan  ke  dalam  wadah  tersebut  diharapkan   dapat  menghasilkan  keuntungan yang maksimum.  Benda­benda  yang   akan  dimasukkan  ini  masing­masing  memiliki  berat  dan  sebuah  nilai  yang  digunakan  untuk  menentukan  prioritasnya  dalam  pemilihan  tersebut.  Nilainya  dapat  berupa  tingkat kepentingan, harga barang, nilai sejarah, atau yang lainnya. Wadah yang  dimaksud  di  sini  juga  memiliki  nilai  konstanta  yang  merupakan  nilai  pembatas  untuk  benda­benda  yang  akan  dimasukkan  ke  dalam wadah tersebut untuk itu harus diambil sebuah  cara  memasukkan  benda­benda  tersebut  ke  dalam  wadah  sehingga  menghasilkan  hasil  optimum tetapi tidak melebihi kemampuan wadah untuk menampungnya.    2.3. Jenis­Jenis ​ Knapsack Problem  Terdapat beberapa variasi ​ Knapsack problem​ , diantaranya:  a. 0/1 Knapsack problem  Setiap barang hanya tersedia 1 unit, ​ take it or leave it​ .  b. Fractional Knapsack problem  Barang  boleh  dibawa  sebagian  saja  (unit  dalam  pecahan).  Versi   problem  ini  menjadi  masuk  akal  apabila  barang  yang  tersedia  dapat  dibagi­bagi   misalnya  gula,  tepung,  dan  sebagainya.  c. Bounded Knapsack problem  Setiap barang tersedia sebanyak N unit (jumlahnya terbatas).  d. Unbounded Knapsack problem  Setiap barang tersedia lebih dari 1 unit, jumlahnya tidak terbatas    2.4. Berbagai Macam Stategi dalam Mengatasi Permasalahan Knapsack  a. Knapsack Problem  Knapsack  sering  sekali   digunakan  terutama  pada  bidang  (jasa)  pengangkutan  barang  (seperti  pengangkutan  peti  kemas  dalam  sebuah  kapal).  Dalam  usaha  tersebut,  diinginkan  suatu  keuntungan  yang  maksimal  untuk  mengangkut  barang  yang  ada  dengan  tidak  melebihi  batas  kapasitas   yang  ada.  Berdasarkan  persoalan  tersebut,  diharapkan ada suatu  solusi  yang  secara  otomatis   dalam  mengatasi  persoalan  itu.  Problem  Knapsack  adalah  permasalahan  optimasi  kombinatorial,  dimana  kita  harus  mencari  solusi  terbaik  dari  banyak  kemungkinan  yang  dihasilkan (Wahab, 2008).  b. Penyelesaian ​ Knapsack  Knapsack  problem  bisa  diselesaikan  dengan  berbagai  cara.  Ada  beberapa  strategi  algoritma yang dapat menghasilkan solusi optimal, diantaranya adalah: 

1) Brute Force  Brute  force  ​ adalah  sebuah  pendekatan  yang  lempang  (​ straightforward​ )  ​ untuk  memecahkan  suatu  masalah,  biasanya  didasarkan  pada  pernyataan  masalah  (​ problem  statement​ ) dan definisi konsep yang dilibatkan (Munir, 2004).  2) Algoritma Greedy  Algoritma  Greedy  merupakan  metode  yang  paling  populer  untuk  memecahkan  persoalan  optimasi  (Munir,  2001).  Dalam  menyelesaikan  permasalahan,  algoritma  Greedy  melakukannya secara bertahap (Brassard G, 1996). Tahap penyelesaiannya adalah:  1) Mengambil  pilihan  yang  terbaik  yang  dapat  diperoleh  pada saat itu tanpa  memperhatikan  konsekuensi ke depan.  2) Berharap  bahwa  dengan  memilih  optimum  lokal  pada  setiap  langkah  akan  berakhir  dengan optimum global.    2.5. Strategi Algoritma Greedy  Untuk  memilih  objek  yang  akan  dimasukkan   ke  dalam  Knapsack,  terdapat  beberapa  strategi Greedy yang heuristik (Silvano, 1990) yaitu:  a. Greedy by profit  Knapsack  diisi  dengan  objek yang  mempunyai keuntungan terbesar pada setiap tahap.  Objek  yang  paling  menguntungkan  dipilih  terlebih  dahulu  untuk  memaksimumkan  keuntungan.  Tahap pertama yang dilakukan adalah mengurutkan  secara menurun objek­objek  berdasarkan  profitnya.  Kemudian  baru  diambil  satu  per­satu  objek  yang  dapat   ditampung  oleh  Knapsack  sampai  Knapsack  penuh  atau  sudah  tidak  ada  objek  lagi  yang  dapat  dimasukkan.  b. Greedy by weight  Knapsack  diisi  dengan  objek  yang   mempunyai  berat  paling  ringan  pada  setiap  tahap.  Sebanyak  mungkin  objek  dimasukkan  ke  dalam  Knapsack  untuk  memaksimumkan  keuntungan.  Tahap  pertama  yang  dilakukan  adalah  mengurutkan   secara  menaik  objek­objek  berdasarkan  ​ weight​ ­nya.  Kemudian  baru  diambil  satu  per­satu  objek  yang  dapat  ditampung  oleh  Knapsack  sampai  Knapsack  penuh  atau  sudah  tidak  ada  objek  lagi  yang  dapat  dimasukkan.  c. Greedy by density  Knapsack  diisi  dengan  objek  yang   mempunyai  densitas  terbesar  pada  setiap  tahap.  Memilih  objek  yang  mempunyai  keuntungan  per­unit  berat  terbesar  untuk  memaksimumkan  keuntungan.  Tahap  pertama  yang  dilakukan adalah mencari nilai profit per­unit (​ density​ ) dari  tiap­tiap objek. Kemudian  objek­objek tersebut diurutkan berdasarkan ​ density​ ­nya. Kemudian  baru  diambil  satu  per­satu  objek  yang  dapat  ditampung  oleh  Knapsack  sampai  Knapsack  penuh atau sudah tidak ada objek lagi yang dapat dimasukkan. Algoritma Greedy mengurangi  jumlah langkah pencarian.   

2.6. Algoritma Greedy dalam Menyelesaikan Masalah Knapsack  Algoritma  Greedy  menyelesaikan  suatu  masalah  dengan  beberapa  fungsi  pembatas  untuk  mencapai  satu   fungsi   tujuan   (Prihandono,  2009).  Jadi  dalam  penyelesaiannya  harus  ditentukan  fungsi  pembatas dan fungsi tujuan. Cara untuk menyelesaiakan masalah Knapsack  dengan algoritma Greedy adalah:  1) Tentukan  Fungsi  Tujuan,  yaitu  mencari  nilai  maksimum  dari  jumlah  hasil  perkalian  antara nilai profit (​ Pi​ ) dengan nilai probabilitas (​ Xi​ ).   

M aximum  ∑ P i × X i    

2) Tentukan  Fungsi  Pembatas,  yang  merupakan  hasil  penjumlahan  dari  perkalian  antara  bobot  (​ Wi​ )  dengan  nilai   probabilitas  (​ Xi​ )  yang  tidak  boleh  melebihi  dari  kapasitas  media  penyimpanan (​ M​ ).   

∑ W i × X i ≤ M , dimana  0 ≤ X i ≤ 1,  P i > 0,  W i > 0    

Berikut ini algoritma Greedy dalam menyelesaikan permasalahan Knapsack:  PROCEDURE GREEDY KNAPSACK (P, W, X, n)  REAL  P(1:n), W(1:n), X(1:n), M, isi  INTEGER i, n  X(1:n) = 0  isi = M  FOR i = 1 TO n DO  IF  W(i) > isi THEN EXIT ENDIF  X(i) = 1  isi = isi – W(i)  REPEAT  IF i ≤ n THEN X(i) = isi/W(i) ENDIF  END GREEDY KNAPSACK 

Keterangan:  n = Jumlah objek  Wi = ​ Bobot setiap objek  Pi = ​ Profit setiap objek  Xi = ​ Probabilitas setiap objek  M = ​ Kapasitas media penyimpanan    3.

METODE PENELITIAN  Langkah­langkah  penelitian  yang  dilakukan  pada  tulisan  ini  untuk  menyelesaikan   permasalahan  knapsack  dalam  pemilihan  peti  kemas  menggunakan  algoritma  greedy  adalah  sebagai berikut:  1) Melakukan  studi  literatur  mengenai  algoritma  greedy  dalam  penyelesaian  permasalahan  knapsack.  2) Mengidentifikasi  permasalahan  atau  kendala  yang  dihadapi  dalam  penerapan  agoritma  greedy. 

3) Melakukan  eksperimen  (​ coding​ ),  yaitu  dengan  membuat  prototipe  menggunakan  bahasa  pemrograman  untuk  mensimulasikan  solusi  permasalahan  knapsack  pada  pemilihan  peti  kemas.  4) Melakukan analisis dan pembahasan dari hasil simulasi menggunakan program yang telah  dibuat.  5) Membuat kesimpulan dari serangkaian kegiatan penelitian yang telah dilakukan.    4.

HASIL DAN PEMBAHASAN  Permasalahan  yang  diambil  pada  tulisan  ini  yaitu  tentang  pemilihan  peti  kemas  yang  akan  dimasukkan  ke  dalam  kapal  pengangkut.  Kapal  pengangkut  ini  memiliki  kapasitas  terbatas,  namun  menginginkan  hasil  atau  keuntungan  yang  besar  dari  pengangkutan  peti  kemas.  Sehingga  petugas  memerlukan  waktu  cukup  lama  untuk  melakukan  perhitungan,  sedangkan kegiatan pengangkutan peti kemas ke dalam kapal harus cepat.  Dari  permasalahan  tersebut  dibuatlah  prototipe  program  untuk  mensimulasikan  pemilihan  peti  kemas  dengan  keuntungan  yang  maksimal.  Kode  program  dibuat  dengan  menggunakan  bahasa  pemrograman  Java  yang  dijalankan  menggunakan  IDE  Eclipse,  algoritma yang digunakan adalah Algoritma Greedy pada Permasalahan Knapsack.  Di bawah ini adalah sintaks dari program yang telah dibuat:  /**    * File name   : Knapsack.java    * Program name: Knapsack Peti Kemas    * By Computer Science Ilkom IPB 2015  */    import java.util.*;  import java.io.*;  import java.lang.*;  public class Knapsack {      static int n = 5, W;      static obj st[];      public static BufferedReader br = new BufferedReader (new  InputStreamReader(System.in));        public static void main(String[] agus) throws IOException {     int i = 0;     System.out.println("Knapsack Problem\n­­­­­­­­­­­­­­­­­­\n");     System.out.print("Banyak peti yang ingin dimasukkan : ");     n = Integer.parseInt(br.readLine());     System.out.print("Kapasitas maksimum kapal (Kg) : ");     W = Integer.parseInt ( br.readLine() );     st = new obj[n];     for (i=0; i
   st[i].p_perKg = Round (st[i].profit / st[i].weight, 2);     System.out.print("\tProfit per Kg: " + st[i].p_perKg + "\n");     st[i].index = i + 1;     }     bubbleSort();     System.out.print("\nSolusi Optimal : ");     fill_sack();      }        public static float Round(float Rval, int Rpl) {     float p = (float) Math.pow(10, Rpl);     Rval = Rval * p;     float tmp = Math.round(Rval);     return(float) tmp / p;      }        static void fill_sack() {     float x[] = new float[n];     float u, tot_profit = 0;     int i;     for (i=0; i u)     break;     x[i] = 1;     u ­= st[i].weight;     System.out.print("\nMemasukkan Peti #" + st[i].index + " (Rp.  " + st[i].profit + " , " + st[i].weight + " Kg) kedalam kapal.\n" );     System.out.print("Kapasitas kapal tersisa : " + u + " Kg\n");     tot_profit += st[i].profit;     }     System.out.print("\n\nTotal Profit earned = Rp." + tot_profit +  "/­");      }        static void bubbleSort() {     for (int pass=1; pass
 

Output ​ yang dihasilkan dari sintaks di atas terlihat seperti Gambar 1. 

  Gambar 1.​  ​ Output ​ Program Greedy Knapsack untuk Pemilihan Peti Kemas  Contoh  kasus  yang  penulis  gunakan  untuk  mensimulasikan  permasalahan  knapsack  pada  peti  kemas  yaitu  jika  terdapat  3  peti  kemas  yang  ingin  dimasukkan  ke  dalam  kapal  pengangkut  dengan  kapasitas   maksimal  sebesar  20  Kg,  dengan  berat  masing­masing  peti  kemas  tersebut  adalah  18  Kg,  15  Kg,  dan  10  Kg,  dimana  setiap  peti  kemas  memiliki  profit  masing­masing sebesar 25, 24, dan 15.  Untuk  memperoleh  keuntungan  yang  maksimal,  langkah­langkah  yang  dilakukan  oleh  algoritma greedy adalah sebagai berikut:  Data yang diketahui:  n = 3, (1, 2, 3) → objek  M = 20 → kapasitas  (W 1,  W 2,  W 3) = (18,  15,  10)   (P 1,  P 2,  P 3) = (25,  24,  15)   Nilai probabilitas ​ 0 ≤ Xi ≤ 1   

Perbandingan profit dengan bobot:  P 1/W 1 = 25/18 = 1.39   P 2/W 2 = 24/15 = 1.6   P 3/W 3 = 15/10 = 1.5   Susun data sesuai kriteria (​ non increasing​ ):  (P 2,  P 3,  P 1) = (24,  15,  25) , atau  (P 1,  P 2,  P 3) = (24,  15,  25)   (W 2,  W 3,  W 1) = (15,  10,  18) , atau  (W 1,  W 2,  W 3) = (15,  10,  18)   Masukkan nilai kriteria di atas ke dalam algoritma greedy:  1) PROCEDURE GREEDY KNAPSACK (P, W, X, n) → nama prosedur/proses  2) REAL  P(1:n), W(1:n), X(1:n), M, isi → variabel yang digunakan  3) INTEGER i, n → variabel yang digunakan  4) X(1:n) = 0  5) isi = M  6) FOR i = 1 TO n DO  7) IF  W(i) > isi THEN EXIT ENDIF  8) X(i) = 1  9) isi = isi – W(i)  10)REPEAT  11)IF i ≤ n THEN X(i) = isi/W(i) ENDIF  12)END GREEDY KNAPSACK → akhir prosedur/proses 

Proses kegiatan dimulai dari langkah ke­ 4 sampai dengan 11.  X(1:3) = 0, artinya X(1)=0, X(2)=0, X(3)=0  isi = M = 20  Pengulangan untuk i = 1 sampai dengan 3  Untuk i = 1  Apakah W(1) > isi  Apakah 15 > 20, jawabnya ​ tidak​ , karena tidak maka perintah dibawah IF dikerjakan.  X(1) = 1 → nilai probabilitas untuk objek pada urutan pertama (X​ )  1​ isi = 20 – 15 = 5  REPEAT → mengulang untuk perulangan FOR  Untuk i = 2  Apakah W(2) > isi  Apakah  15  >  5,  jawabnya  ​ ya​ ,  karena  ya  maka  perintah  EXIT  dikerjakan,  yaitu  keluar  dari  pengulangan/FOR dan mengerjakan perintah di bawah REPEAT.  Apakah  2  ≤  3,  jawabnya  ​ ya​ ,  karena  ya  maka  X(2)  =  5/10  =  ½  →  nilai  probabilitas  untuk  objek pada urutan kedua (X​ ).  2​ Selesai (akhir dari prosedur greedy knapsack).  Berarti  untuk  nilai  X(3)   =  0  atau  X​ 3   =   0,   sebab  nilai  probabilitas  untuk  objek  ke­3  tidak  pernah dicari. 

  Jadi  (P 1,  P 2,  P 3) = (24,  25,  25)   (W 1,  W 2,  W 3) = (15,  10,  18)   (X 1,  X 2,  X 3) = (1,  1/2,  0)   Fungsi Pembatas:   

∑ W i × Xi ≤ M    

(W 1 × X 1) + (W 2 × X 2) + (W 3 × X 3) ≤ M   (15 × 1) + (10 × 1/2) + (18 × 0) ≤ 20   20 ≤ 20   Fungsi Tujuan:   

∑ P i × X i = (P 1 × X 1) + (P 2 × X 2) + (P 3 × X 3)    

= (24 × 1) + (15 × 1/2) + (25 × 0)   = 31.5   Hasil akhir dari program yang telah dijalankan, mendapatkan data seperti pada Tabel 1.  Tabel 1.​  Hasil akhir program Greedy Knapsack  Properti Objek 

Greedy by 

N  1  2 

Wi  18  15 

Pi  25  24 

Pi/Wi  1.39  1.6 

Profit  1  0 

Weight  1  0 

Density  0  1 

3  Total Bobot 

10 

15 

1.5 

0  18 

0  18 

0  15 

Total Keuntungan  25  25  24    Dari  Tabel  1 terlihat bahwa ​ greedy by profit ​ dan ​ greedy by weight  ​ memiliki keuntungan lebih  besar.  Namun  apabila  diperhatikan  secara  seksama,  ​ greedy  by  density  ​ yang  lebih  optimal,  karena  dengan  bobot  yang  kecil  keuntungan yang diperoleh lebih besar dibandingkan  dengan  greedy  by  profit  ​ dan  ​ greedy  by  weight​ .  Sehingga  dari  analisis  di  atas  diperoleh  bahwa   algoritma ​ Greedy ​ dapat memberikan solusi optimal pada program pemilihan peti kemas.    5.

KESIMPULAN  Knapsack  merupakan  salah  satu  permasalahan  yang  dapat   diselesaikan  dengan  strategi  greedy,  untuk  mencari  dan  mendapatkan  solusi  optimal  yaitu  dengan  menggunakan  strategi  ​ greedy  by  profit​ ,  ​ greedy  by  weight​ ,  atau  juga  dapat  diselesaikan  dengan  ​ greedy  by  density​ .  Pendekatan  yang  digunakan  oleh  algoritma  greedy  adalah  membuat   pilihan  yang  dapat  memberikan  perolehan  terbaik,  yaitu  dengan  membuat  pilihan  optimum  lokal  pada 

setiap  langkah  dengan  tujuan  bahwa  sisanya  mengarah  ke  solusi  optimum  global.  Meskipun  tidak  selalu  mendapatkan  solusi  terbaik  (optimum),  algoritma  greedy  umumnya  memiliki  kompleksitas  waktu  yang  cukup  baik,  sehingga  algoritma  ini  sering  digunakan  untuk  kasus  yang memerlukan solusi cepat meskipun tidak optimal seperti sistem ​ real­time ​ atau ​ game​ .  Pada  permasalahan  optimasi  peti  kemas,  algoritma  greedy  diterapkan  sebagai  salah  satu  cara  untuk  menyelesaikan  permasalahan knapsack pada pemilihan peti kemas. Dari hasil  percobaan  dan  analisis  yang  telah  dilakukan,  algoritma  greedy  memberikan  solusi  optimal  dalam  melakukan  pemilihan  peti  kemas  sehingga  juga  diperoleh  keuntungan  yang  lebih  besar.    6. DAFTAR PUSTAKA  Brassard G. 1996. ​ Fundamentals of algorithmics​ . New Jersey: Prentice­Hall.  Indrianingsih,  Y.  ____.  ​ Algoritma  Genetik   Untuk  Seleksi  Peti  Kemas  Pada  Pelabuhan.  (Online).  (​ http://stta.name/data_lp3m/JURNAL­ANGKASA­PETI­KEMAS.doc​ ,  diakses 9 Januari 2016)  Munir,  R.  2001.  ​ Algoritma  dan  Pemrograman  dalam  bahasa  pascal  dan  C​ .  Bandung:  CV.  Informatika.  Munir,  R.  2004.  ​ Bahan  Kuliah  ke­1  IF2251:  Strategi Algoritmik dan Algoritma Brute  Force​ .  Departemen  Teknik   Informatika  Institut  Teknologi  Bandung.  (Online).  (​ http://kur2003.if.itb.ac.id/file/trans­Bahan Kuliah ke­1.doc​ , diakses 10 Januari 2016).  Prihandono,  H.  2009.  ​ Knapsack  Problem  dengan  Algoritma  dan  Metode   Greedy​ .  (Online).  (​ https://hendryprihandono.files.wordpress.com/2009/01/knapsack­problem­metode­gr eedy.doc​ , diakses 10 Januari 2016).  Silvano  et  al.  1990.  ​ Knapsack  problem:  Algorithm  and  Computer  Implementation​ .  John  Wiley & Sons. ISBN: 0­471­92420.  Wahab,  A.,  Shinta,  P.,  dkk.  2008.  ​ Knapsack  Algorithm  &  Computer  Implementation​ .  (Online). (​ http://oc.its.ac.id/ambilfile.php?idp=667​ , diakses 10 Januari 2016)