Knapsack Problem

METODE GREEDY banyak digunakan dalam berbagai penyelesaian maslah, antara lain adalah :

1.    Optimal Storage on Tapes Problem

2.    Kanpsack Problem

3.    Minimum Spanning Tree Problem

4.    Shortest Path Problem

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.

Contoh kasus knapsack

§  w1 = 10;  p1 = 2

§  w2 = 5;     p2 = 3

§  w3 = 15;   p3 = 5

§  w4 = 7;     p4 = 7

§  w5 = 6;     p5 = 1

§  w6 = 18;   p6 = 4

§  w7 = 3;     p7 = 1

M = 15

Jawaban :

Kesimpulan : Pada soal ini, algoritma greedy dengan strategi pemilihan objek berdasarkan profit memberikan solusi optimal, sedangkan pemilihan objek berdasarkanweight dan density tidak memberikan solusi optimal.

Pseudo_code :

Sumber :

http://gbaruchkrisnanta.blogspot.co.id/2015/06/metode-greedy-divide-and-conquer.html?m=1