Knapsack Problem

Knapsack Problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang di mana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum.

Knapsack Problem bisa kita gambarkan, misalnya kita mempunyai sebuah kantong atau tas dengan kapasitas tertentu sedangkan dihadapan kita terdapat begitu banyak pilihan barang, maka kita harus memilih barang mana saja yang kira-kira akan kita angkut sesuai kapasitas kantong yang kita miliki supaya kita bisa mendapatkan keuntungan yang sebesar-besarnya atau maksimal.

Dalam menghadapi masalah di atas, metode Greedy memiliki 3 pilihan strategi pengangkutan, yaitu:

• Greedy by Profit, strategi ini mengharapkan keuntungan maksimal dengan cara memasukan barang atau objek dengan nilai keuntungan terbesar terlebih dahulu ke dalam kantong atau knapsack. Jadi strategi ini hanya mempertimbangkan jumlah keuntungan dari sekumpulan barang, dengan catatan berat barang yang akan dibawa tidak melebihi kapasitas kantong yang kita miliki.
• Greedy by weight, pada strategi ini kita berusaha memasukan barang sebanyak-banyaknya kedalam kantong, jadi barang atau objek yang dimasukan terlebih dahulu adalah barang dengan bobot paling ringan terlebih dahulu, dengan harapan dengan banyaknya barang atau objek yang terangkut kita bisa mendapatkan keuntungan sebesar-besarnya.
• Greedy by density, strategi ini mengharapkan keuntungan sbesar-besarnya dengan memasukan barang  yang memiliki keuntungan per unit terbesar (Pi/Wi) terlebih dahulu kedalam kantong.  

Contoh 1 :

       Seorang pencuri ingin mencuri perhiasan di sebuah toko perhiasan, di toko tersebut perhiasan-perhiasan itu ditempatkan pada 4 buah kotak, setiap kotak perhiasan memiliki bobot perhiasan berbeda-beda(w₁=3, w₂=5, w₃=6, w₄=10) dan memiliki keuntungan berbeda-beda(p₁=15, p₂=25, p₃=24, p₄=50) tetapi pencuri itu hanya membawa sebuah tas yang hanya bisa menampung maksimal (W_max=20). Bagaimana caranya pencuri itu dalam mengambil perhiasan-perhiasan tersebut dengan mempertimbangkan keuntungan maksimal yang dapat diperoleh.

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	Pi/wi	profit	weight	density
1	3	15	5	1	1	1	1
2	5	25	5	1	0	1	1
3	6	24	4	0	1	0	0
4	10	50	5	1	1	1	1
Total Bobot				18	19	18	18
Total Keuntungan				90	89	90	90

nb:
->  1 menandakan barang dimasukan
->  0 menandakan barang tidak dimasukan
->  pada bagian "profit" utamakan memasukan jumlah barang agar mendekati keuntungan maksimal
->  pada bagian " weight" utamakan memasukan jumlah barang agar mendekati beban maksimal
-> pada bagian " density" utamakan memasukan jumlah barang agar mendekati harga keuntungan per-unit barang maksimal.

Contoh 2 :

       Seseorang penjual memiliki lima buah tempat sayuran yang isinya memiliki bobot berbeda(w₁=2, w₂=4, w₃=5, w₄=3, w₅=7) dan harga yang tentunya berbeda pula(p₁=12, p₂=8, p₃=15, p₄₌12_, p₅=14). Ia ingin menjual sayuran dengan berbagai macam sayuran berbeda dalam satu buah kantung yang bisa menampung beban maksimal(W_max=12). Bagaimana penjual itu mengatur nya agar penjual itu bisa mendapat keuntungan maksimal.

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	Pi/wi	profit	weight	density
1	2	12	6	1	0	1	1
2	4	8	2	0	0	0	0
3	5	15	3	1	1	1	1
4	3	12	4	1	0	1	1
5	7	14	2	0	1	0	0
Total Bobot				10	12	10	10
Total Keuntungan				39	29	39	39

nb:

->  1 menandakan barang dimasukan

->  0 menandakan barang tidak dimasukan

->  pada bagian "profit" utamakan memasukan jumlah barang agar mendekati keuntungan maksimal

->  pada bagian " weight" utamakan memasukan jumlah barang agar mendekati beban maksimal

->  pada bagian " density" utamakan memasukan jumlah barang agar mendekati harga keuntungan           per-unit barang maksimal.

Referensi :

http://bloglogika.blogspot.co.id/2011/01/knapsack-problem.html

https://kevinkarundeng.wordpress.com/2012/11/05/contoh-soal-algoritma-greedy-dan-knapsack-problem/