Listing
#include
#include
#define size 100
void sort(int[], int);
main()
{
clrscr();
int x[size],i,n,uang,hasil[size];
printf("\n Banyak Koin :");
scanf("%d", &n);
printf("\n \n Masukkan Jenis Koin : \n");
for(i=1;i<=n;i++)
{
scanf("%d", &x[i]);
}
sort(x,n);
printf("\n Koin yang Tersedia :");
for(i=1;i<=n;i++)
{
printf("%d", x[i]);
printf("\n");
}
printf("\n");
printf("\n Masukkan Nilai yang Dipecah :");
scanf("%d", &uang);
printf("\n");
for(i=1;i<=n;i++)
{
hasil[i]=uang/x[i];
uang=uang%x[i];
}
for(i=1;i<=n;i++)
{
printf("Keping %d", x[i]);
printf("-an sebanyak : %d", hasil[i]);
printf("\n \n");
}
getch();
return 0;
}
void sort(int a[], int siz)
{
int pass,hold,j;
for(pass=1;pass<=siz-1;pass++)
{
for(j=0;j<=siz-2;j++)
{ if(a[j+1] < a[j+2])
{
hold=a[j+1];
a[j+1]=a[j+2];
a[j+2]=hold;
}
}
}
}
Logika
1. Definisi
Algoritma greedy adalah algoritma yang memecahkan masalah langkah demi langkah, pada setiap langkah:
1. mengambil pilihan yang terbaik yang dapat diperoleh saat itu
2. berharap bahwa dengan memilih optimum lokal pada setiap langkah akan mencapai optimum global.
Algoritma greedy mengasumsikan bahwa optimum lokal merupakan bagian dari optimum global. Prinsip algoritma greedy adalah: “take what you can get now!”. Ambil apa yang anda peroleh sekarang! Prinsip ini juga dipakai dalam pemecahan masalah optimasi.
Ø Persoalan optimasi (optimization problems): persoalan yang menuntut pencarian solusi optimum.
Ø Persoalan optimasi ada dua macam:
1. Maksimasi (maximization)
2. Minimasi (minimization)
Ø Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.
Ø Elemen persoalan optimasi:
1. kendala (constraints)
2. fungsi objektif(atau fungsi optiamsi)
Ø Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum
Ø Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi
Ø Algoritma greedy membentuk solusi langkah per langkah (step by step).
.
2. Penjelasan listing
#include
#include
- berfungsi untuk memasukkan suatu library file melalui header file kedalam program.
- Header file yg dimaksud adalah stdio.h dan conio.h.
void sort(int[], int);
- merupakan sebuah bentuk deklarasi fungsi dengan ‘sort’ yg bertipe void (tidak mengembalikan nilai).
- Statement ini diperlukan karena fungsi tersebut didefinisikan stelah fungsi utama (main).
void sort(int a[], int siz){
int pass,hold,j;
for(pass=1;pass<=siz-1;pass++){
for(j=0;j<=siz-2;j++){
if(a[j+1] < a[j+2]){
hold=a[j+1];
a[j+1]=a[j+2];
a[j+2]=hold;
}}}}
- merupakan definisi fungsi dari fungsi ‘sort’, fungsi ini akan memecah mata uang menjadi nilai yg lebih kecil berdasarkan jenis-jenis pecahan koin yg teersedia.
- Sementara inti dari konsep greedy-nya adalah meminimalisir jumlah koin pecahan sehingga koin pecahan tidak terlalu banyak.
clrscr();
int x[size],i,n,uang,hasil[size];
printf("\n Banyak Koin :");
scanf("%d", &n);
- perintah dimulai untuk membersihkan layar, dan deklarasi variabel i, n, uang bertipe integer dan x, hasil bertipe array dengan size sebagai masing-masing indeksnya.
- selanjutnya program akan akan meminta input berapa banyaknya koin yg ada.
printf("\n \n Masukkan Jenis Koin : \n");
for(i=1;i<=n;i++){
scanf("%d", &x[i]);
}
- perintah ini akan meminta jenis-jenis koin yg ada, perintah ini akan mengulang berdasarkan banyaknya koin yg dimasukkan sebelumnya yaitu berdasarkan nilai dari variabel n.
sort(x,n);
printf("\n Koin yang Tersedia :");
for(i=1;i<=n;i++){
printf("%d", x[i]);
printf("\n");
}
printf("\n");
- selanjutnya program akan memanggil fungsi ‘sort’ yg telah telah didefinisikan sebelumnya, lalu program akan menampilkan koin-koin yg tersedia. Jumlah koin yg tersedia ditampilkan berdasarkan banyaknya koin.
printf("\n Masukkan Nilai yang Dipecah :");
scanf("%d", &uang);
printf("\n");
for(i=1;i<=n;i++){
hasil[i]=uang/x[i];
uang=uang%x[i];
}
- perintah ini berfungsi meminta input nominal mata uang untuk selanjutnya dipecah menjadi pecahan yg lebih kecil.
for(i=1;i<=n;i++){
printf("Keping %d", x[i]);
printf("-an sebanyak : %d", hasil[i]);
printf("\n \n");
}
- perintah ini berfungsi untuk menampilkan jumlah pecahan mata uang yg lebih kecil yg tersedia dan mengelompokkannya berdasarkan algoritma greedy. Sehingga tidak ada jumlah pecahan mata uang tidak terlalu banyak.
Output
0 Comments