Algoritma greedy adalah algoritma yang menentukan hasil optimum berdasarkan optimal lokal dari kasus tanpa melihat efek dari pemilihan tersebut. Secara gampangnya, bila dengan algoritma ini bisa ditemukan kondisi optimum lokal dari sebuah masalah, diharapkan optimum global dapat ditemui dari solusi optimum lokal sebelumnya. Sebagai contoh, dalam kasus penukaran uang, dimana terdapat pecahan uang {100,100,100,100,100, 500,500, 1000, 1000, 5000} dan kita ingin menukarkan uang 7000 untuk mendapat hasil penukaran seminimum mungkin, maka pastinya kita memilih pecahan 5000 dan 2x 1000. Algoritma greedy memiliki kelebihan lebih efisien dan lebih mudah untuk digunakan. Tetapi, ada kasus dimana algoritma greedy tidak dapat digunakan. Semisal kita memiliki pecahan uang (anggap kita memiliki pecahan uang 1500) {100,100,100,100,100,1000,1000,1500} dan kita ingin menukarkan uang 2000. Solusi dengan menggunakan greedy akan memaksa kita untuk memilih {1500,100,100,100,100,100} padahal ada solusi yang lebih baik daripada itu {1000,1000}. Tetapi walaupun algoritma greedy memiliki kekurangan, algoritma ini dapat digunakan untuk memecahkan problem2 seperti : TSP, combinatorial problem, serta fractional knapsack. Pada postingan ini akan dibahas mengenai penggunaan greedy untuk memecahkan problem fractional knapsack. Semoga bermanfaat… 😀
Berikut sedikit pembahasan mengenai Fractional Knapsack. Anggap ada seorang pencuri yang membawa tas dengan kapasitas sebesar N. Pencuri tersebut dihadapkan oleh beberapa pilihan serbuk emas yang memiliki berat (b[i]) dan harga (h[i]) yang berbeda2. Dengan kapasitas tas yang terbatas, bagaimanakah cara pencuri tersebut mengisi tasnya untuk mendapat hasil se optimal mungkin?
Untuk permasalahan diatas, sebelumnya perlu diketahui bahwa kita dapat mengambil sebagian dari barang yang ada. Berbeda dengan 0-1 knapsack dimana kita tidak dapat mengambil sebagian dari barang yang tertera pada masalah. Solusi paling klasik dari permasalahan diatas yaitu dengan membagi harga (h[i]) barang dengan beratnya (b[i]) sehingga bisa didapatkan rasio harga/berat. Setelah itu, rasio tersebut diurutkan dari yang terbesar ke yang terkecil, untuk kemudian diambil satu per satu selama masih dapat masuk dalam kapasitas tas. Ketika sisa kapasitas < berat barang, kita dapat mengambil bagian dari barang tersebut dan menambahkan total valuenya dengan sisaKapasitas/b[i]*h[i].
Semisal diberi inputan :
int banyak=5;
int berat[]={12, 1, 2, 1, 4};
int harga[]={4, 2, 2, 1, 10};
int beratMax=15;
Maka output yang dihasilkan :
Memasukkan 4 kg ke dalam knapsack, besar value = 10, sisa = 11
Memasukkan 1 kg ke dalam knapsack, besar value = 12, sisa = 10
Memasukkan 1 kg ke dalam knapsack, besar value = 13, sisa = 9
Memasukkan 2 kg ke dalam knapsack, besar value = 15, sisa = 7
Memasukkan 58.3 % berat 12 kg sisa ke dalam knapsack, besar value = 17.3, sisa 0
Total = 17.3, sisa knapsack = 0
Berikut adalah kode knapsack dengan pendekatan greedy dengan menggunakan bahasa C :
#include<stdio.h>
#include<stdlib.h>
int banyak=5;
int berat[]={12, 1, 2, 1, 4};
int harga[]={4, 2, 2, 1, 10};
int beratMax=15;
int main(){
float fractional[banyak];
for(int a=0;a<banyak;a++){
fractional[a]=(float)harga[a]/berat[a];
}
for(int a=0;a<banyak-1;a++){
for(int b=a+1;b<banyak;b++){
if(fractional[b]>fractional[a]){
float temp=fractional[a];
fractional[a]=fractional[b];
fractional[b]=temp;
int temp2=berat[a];
berat[a]=berat[b];
berat[b]=temp2;
temp2=harga[a];
harga[a]=harga[b];
harga[b]=temp2;
}
}
}
int index=0;
int total=0;
float sisa=0;
while(beratMax&&index<banyak){
if(berat[index]<beratMax){
printf(“Memasukkan %d kg ke dalam knapsack, besar value = %d, sisa=%d\n”,berat[index],total+=harga[index],beratMax-=berat[index]);
index++;
}
else{
sisa=(float)beratMax/berat[index];
printf(“Memasukkan %g %% berat %d sisa kg ke dalam knapsack, besar value = %f, sisa=%d\n”,sisa*100,berat[index],(float)total+sisa*harga[index],0);
sisa=(float)total+sisa*harga[index];
index++;
}
}
printf(“Total = %f, sisa knapsack = %d\n”,sisa,0);
system(“pause”);
return 0;
}
Bleau et Rouge... 