KNAPSACK PROBLEM

Resume Individu: KNAPSACK PROBLEM

Nama: Komarudin Tasdik

NRP: G651100341

Penyaji:

Pritasari Palupiningsih, dkk. 2010. Slide Presentasi: Mengenal 0 – 1 Knapsack Problem. Institut Pertanian Bogor: Departemen Ilmu Komputer

  • Knapsack Problem adalah permasalahan seseorang yang dibatasi kapasitas knapsack yang tetap dan harus diisi dengan item yang sangat bernilai.
  • Implementasinya: Pengisian barang di gudang, optimalisasi karyawan dalam suatu perusahaan, dll.
  • Jenis knapsack problem yang dibahas: 0-1 Knapsack Problem. Item-item knapsack ini bersifat indivisible (tidak dapat dibagi) dan dapat diselesaikan menggunakan algoritma dynamic programming
  • 0 – 1 Knapsack: (0) item tidak diambil, (1) item diambil.
  • W: kapasitas knapsack
  • Setiap item i memiliki bobot w dan bernilai c (w dan c adalah integer)
  • Algoritma 0-1 Knapsack

for w = 0 to W

c[0,w] = 0

for i = 1 to n

c[i,0] = 0

for w = 1 to W

if wiw

if vi + c[i-1,wwi] > c[i-1,w]

c[i,w] = vi+ c[i-1,wwi]

else

c[i,w] = c[i-1,w]

else c[i,w] = c[i-1,w]

  • Contoh
i 1 2 3
wi 2 4 1
vi 3 4 3

n  = 3

W = 3

Hasilnya:

Untuk mengetahui isi dari knapsack yang menghasilkan optimal profit, dilakukan cara berikut :

c(3,3) = 6 > c(2,3)  , maka   i3 =  1

c(3,3) = 6 = 3+ c(2,2)

c(2,2) = 3  =  c(1,2) , maka  i2 =  0

c(1,2) = 3 > c(0,2)  , maka   i1 =  1

c(1,2) = 3 = 3+ c(0,0)

Dengan demikian, knapsack berisi (1,0,1)

Dengan weight = 2 +1 = 3

Value =  3 + 3 = 6

 

***

Terima kasih kepada teman-teman penyaji. Apabila ada kesalahan dalam resume ini, mohon koreksinya.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s