zao no hibi

kuliah DAA selasa 17 november 2009

dua hari lalu, tepatnya hari selasa 17 november 2009, gw kuliah DAA seperti biasa.. biasanya kuliah DAA 2 slot itu berasa lamaaaaa banget, tapi entah kenapa, selasa kemaren tuh cukup seru dan tau2 udah jam stngah 10..

hah? cukup seru? are you sure?

hehehe, gimana ga seru? kuliahnya tentang ngemaling :p
di postingan blog gw kali ini, gw mau agak jorok nih..
peringatan keras: kalo ga mau baca hal2 yg jorok, jangan lanjutkan scroll ke bawah.. ingat, anda sudah saya peringatkan. jika anda masih scroll ke bawah dan membaca postingan ini, berarti anda sudah siap menerima resiko kalau hal2 jorok itu akan tersangkut di otak anda, selamanya >:) nyahahaha

Knapsack Problem, terdiri dari 2:
1. 0-1 Knapsack Problem

A thief robbing a store finds n items; the i-th item is worth vi rupiahs and weighs wi kgs, where vi and wi are integers. The thief wants to take as valuable a load as possible, but is only able to carry at most W kgs in his or her knapsack (W is an integer). Which items should the thief take?

intinya sih kek gini:
- ambil item, atau tidak sama sekali (item tidak dapat dipecah-pecah, anggap saja item adalah emas batangan yang akan susah jika harus dipotong terlebih dahulu jika ingin mencurinya)
- muatan di dalam kantong maling tidak boleh lebih besar daripada kapasitas kantong tersebut

2. Fractional Knapsack Problem

The setup is the same as above, but the thief can take fractions of items, rather than having to make a binary (0-1) choice for each item.

intinya sih kek gini:
- ambil item dari yang paling mahal
- jika kantong maling masih muat, ambil yang paling mahal dari item yang tersedia, walaupun tidak semua item bisa diangkut (item dapat dipecah-pecah, anggap saja item adalah serbuk emas, jadi tidak harus diambil semua untuk mencurinya). Tidak semua disini maksudnya, cuma bisa sebagian sampai kantong malingnya penuh.


Untuk lebih memahami, coba pakai contoh aja..
misalkan ada seorang maling dengan kantong maling yang berkapasitas 50 kg. dan ada 3 jenis barang:
item 1: 10 kg, harga 10 kg item tersebut Rp 60 milyar
item 2: 20 kg, harga 20 kg item tersebut Rp 100 milyar
item 3: 30 kg, harga 30 kg item tersebut Rp 120 milyar

Jika menggunakan 0-1 Knapsack Problem, maling dapat memilih:
a. Mengambil item 1 & item 2 (10 kg + 20 kg) dengan harga: Rp 60 milyar + Rp 100 milyar = Rp 160 milyar atau
b. Mengambil item 1 & item 3 (10 kg + 30 kg) dengan harga: Rp 60 milyar + Rp 120 milyar = Rp 180 milyar atau
c. Mengambil item 2 & item 3 (20 kg + 30 kg) dengan harga: Rp 100 milyar + Rp 120 milyar = Rp 220 milyar.

Tentu saja, misalnya saya adalah malingnya, saya akan memilih pilihan yang c, sehingga saya mendapatkan uang Rp 220 milyar >:) ahahaha

Jika menggunakan Fractional Knapsack Problem, maling akan mengambil:
a. Item 1 (semuanya, yaitu 10 kg) dengan harga: Rp 60 milyar dan
b. Item 2 (semuanya, yaitu 20 kg) dengan harga: Rp 100 milyar dan
a. Item 3 (sebagian, yaitu 20 kg) dengan harga: Rp 80 milyar.

Tentu saja, misalnya saya adalah malingnya, saya akan mendapatkan uang Rp 240 milyar >:) ahahaha

Dan pastinya, saya lebih memilih menggunakan metode yang kedua, yaitu Fractional Knapsack Problem..


postingan yang jorok bukan? XD hahahaha..
sudah saya peringatkan sebelumnya bukan? :p

~happy stealing >:)

posted by vonnzaoldyeck @ 1:35:00 PM

Still my heart quiet my soul, slow my speech awaken my ears to the melody of Your voice. Stretch out my arms take hold of my spirit, anchor my being in the depths of Your love. Help me God, to know You more, to love You most, to serve You better. [Deuteronomy 6:5 - You shall love the Lord your God with all your heart, and with all your soul, and with all your might]. Have a blessed day, God bless you :)