File Header dan Fungsinya serta contoh Program pada C++

          Pada bahasa pemrograman C++,dibutuhkan file header agar dapat mengakses memori.File header adalah file yang berisi deklarasi,baik berupa konstanta,standard input output,maupun sebagai syntax. File header pada C++ digunakan untuk memanggil library-library yang ada sehingga suatu fungsi dapat digunakan dengan baik dan benar.Adapun macam-macam file header sebagai berikut :

Include "iostream.h"
Menjalankan perintah-printah berikut :

• Cout merupakan fungsi keluaran yang digunakan untuk menampilkan data ataupun informasi.
• Cin merupakan fungsi masukkan yang digunakan untuk menyimpan data dalam suatu variable.
• Endl merupakan fungsi yang digunakan untuk perpidahan baris.

Contoh program :

#include  <iostream.h>
void main()
{
char nama[30];
cout<<"<<---------------!==Techno-Logic==!--------------->>"<<endl;
cout<<"Nama Kamu : ";
cin>>nama;
cout<<"Nama kamu adalah "<<nama;
}

Include "stdio.h"
Menjalankan perintah-printah berikut :

• Printf merupakan fungsi keluaran untuk menampilkan informasi.
• Scanf merupakan fungsi masukkan yang digunakan menyimpan data pada suatu variable.
• Gets merupakan fungsi masukkan seperti scanf,namun fungsi ini dapat membaca karakter spasi tidak seperti scanf.

Contoh Program :

#include <stdio.h>
void main()
{
    char nama[30],nama2[30];
    printf("<<---------------!==Techno-Logic==!--------------->>");
    printf("\nNama Anda : ");
    scanf("%s",nama);
    printf("Nama anda %s",&nama);
}

#include <stdio.h>
void main()
{
    char nama[30],nama2[30];
    printf("<<---------------!==Techno-Logic==!--------------->>");
    printf("\nNama Anda : ");
    gets(nama);
    printf("Nama anda %s",nama);
}

Include "conio.h"
Menjalankan perintah-perintah sebagai berikut :

• Getch merupakan fungsi untuk menahan tampilan.
• Clrscr merupakan fungsi untuk membersihkan layar.
• Getche merupakan fungsi untuk membaca sebuah karakter dengan sifat karakter yang dimasukkan tidak perlu diakhiri dengan menekan tombol ENTER, dan karakter yang dimasukan ditampilkan di layar.
• Putch merupakan fungsi untuk menampilkan karakter ASCII dari nilai x ke layer monitor tanpa memindahkan letak kursor ke baris berikutnya.
• Clreol merupakan fungsi untuk membersihkan layar mulai dari posisi kursor hingga kolom terakhir, posisi kursor tiak berubah.
• Gotoxy merupakan fungsi untuk memindahkan kursor ke kolom x, baris y.
• Wherex merupakan fungsi untuk mengembalikan posisi kolom kursor.
• Wherey merupakan fungsi untuk mengembalikan posisi baris kursor.
• Window merupakan fungsi untuk mendefinisikan sebuah window berdasarkan koordinat kiri atas dan kanan bawah.

Contoh Program :

#include <stdio.h>
#include <conio.h>
void main()
{
    char nama[30],nama2[30];
    printf("<<---------------!==Techno-Logic==!--------------->>");
    printf("\nNama Anda : ");
    gets(nama);
    clrscr();
    printf("<<---------------!==Techno-Logic==!--------------->>");
    printf("Nama anda %s",nama);
    getch();
}

Include "string.h"
Menjalankan perintah-perintah sebagai berikut :

• Strcpy merupakan fungsi untuk menyalin string..
• Strlen merupakan fungsi untuk mengetahui panjang karakter.
• Strcmp merupakan fungsi untuk membandingkan dua buah string.Hasil dari fungsi ini bertipe integer dengan nilai negative, jika string pertama kurang dari string kedua. Nol, jika string pertama sama dengan string kedua Positif, jika string pertama lebih besar dari string kedua.
• Strupr merupakan fungsi untuk membuat karakter string menjadi huruf kapital.
• Strlwr merupakan fungsi untuk membuat karakter string menjadi huruf kecil.
• Strcat merupakan fungsi untuk menggabungkan karakter string.

Contoh Program :

#include <stdio.h>
#include <string.h>
void main()
{
    char nama[30],nama2[30];
    printf("<<---------------!==Techno-Logic==!--------------->>");
    printf("\nNama Anda : ");
    gets(nama);
    strcpy(nama2,nama);
    printf("Nama anda %s",nama2);
}

Include "math.h"
Menjalankan perintah-perintah sebagai berikut :

• Pow merupakan fungsi untuk mencari pangkat dari suatu nilai.
• Sqrt merupakan fungsi untuk mencari akar dari suatu nilai.
• Max merupakan fungsi untuk menentukan bilangan terbesar dari dua buah bilangan.
• Min merupakan fungsi untuk menentukan bilangan terkecil dari dua buah bilangan.
• Sin,Cos,Tan masing-masing digunakan untuk menghitung nilai sinus, cosinus dan tangens dari suatu sudut.

Contoh Program :

#include <stdio.h>
#include <iostream.h>
#include <math.h>
#include <string.h>
void main()
{
    int nilai,akar,pangkat;
    printf("<<---------------!==Techno-Logic==!--------------->>");
    printf("\nMasukkan Nilai : ");
    cin>>nilai;
    pangkat = pow(nilai,2);
    akar = sqrt(nilai);
    cout<<"Pangkat dari nilai "<<nilai<<" adalah "<<pangkat<<endl;
    cout<<"Akar dari nilai "<<nilai<<" adalah "<<akar<<endl;
}

Include "windows.h"
Menjalankan perintah-perintah sebagai berikut :

• System merupakan fungsi untuk memberikan warna pada form.

Contoh Program :

#include "windows.h"
main()
{
    system("color 4f");
}

Include "iomanip.h"
Menjalankan perintah-perintah sebagai berikut :

• Setiosflags merupakan suatu fungsi manipulator yang digunakan untuk mengatur sejumlah format keluaran data.
• Setw merupakan fungsi untuk mengatur lebar variable.
• Ios::left merupakan fungsi untuk mengatur pertaan sebelah kiri.
• Ios::right merupakan fungsi untuk mngatur perataan sebelah kanan.

Contoh Program :

#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
main()
{
int a = 87, b = 32;
clrscr();
cout<<"<<---------------!==Techno-Logic==!--------------->>";
cout<<"Penggunaan ios::left dan ios::right \n\n";
cout<<"Rata Sebelah Kiri = ";
cout<<setiosflags(ios::left)<<setw(10)<<a;
cout<<setiosflags(ios::left)<<setw(10)<<b<<endl;
cout<<"Rata Sebelah Kanan = ";
cout<<setiosflags(ios::right)<<setw(10)<<a;
cout<<setiosflags(ios::right)<<setw(10)<<b;
getch();
}

Include "stdlib.h"
Menjalankan perintah-perintah sebagai berikut :

• Atof merupakan fungsi untuk mengkonfersi nilai string menjadi bilangan bertipe double.
• Atoi merupakan fungsi untuk merubah tipe data string menjadi integer. 
• Pow merupakan fungsi untuk pemangkatan suatu bilangan.

Include "assert.h" 

Digunakan untuk membantu mendeteksi kesalahan logis dan jenis lain dari bug dalam debugging versi dari sebuah program.

Include "complex.h"
Sebuah set fungsi untuk memanipulasi bilangan kompleks.

Include "ctype.h"
Mendefinisikan set fungsi yang digunakan untuk mengklasifikasikan karakter dengan jenis mereka atau untuk mengkonversi antara atas dan huruf kecil dengan cara yang independen dari yang digunakan set karakter (biasanya ASCII atau salah satu ekstensi, meskipun implementasi menggunakan EBCDIC juga dikenal).

Include "errno.h"
Untuk menguji kode kesalahan dilaporkan oleh fungsi perpustakaan.

Include "fenv.h"
Untuk mengendalikan floating-point lingkungan.

Include "float.h"
Menentukan implementasi khusus properti dari floating-point library.

Include "inttypes.h"
Mendefinisikan tipe bilangan bulat lebar yang tepat.

Read More

Pewarnaan (Coloring)

Pewarnaan (Coloring)

          Pewarnaan yang kita bahas kali ini adalah sebuah cara yang digunakan untuk menyelesaiakan proses panjadwalan. Dimana dalam pewarnaan ini akan digambarkan dengan graph yang terdiri atas simpul, dan ruas Dalam kehidupan sehari-hari sering kali kita dipusingkan oleh rumitnya penjadwalan, misalnya jika kita harus membuat jadwal ujian dimana ada beberapa mahasiswa yang mengikuti beberapa mata kuliah, tentunya agar mahasiswa tersebut dapat mengikuti semua ujian, maka mata kuliah yang diambil secara bersamaan oleh satu siswa tersebut tidak boleh dijadwalkan pada hari dan jam yang sama. Atau misalnya kita mendapatkan proyek untuk membuat lampu lalulintas di sebuah perlimaan, maka kita harus mengatur nyala lampu merah dan hijau agar tidak terjadi tabrakan. Saat ini kita akan belajar bersama salah satu metode untuk mengatasi permasalahan tersebut dengan metode pewarnaan (Coloring).

Problema pemberian warna kepada semua simpul, sedemikian sehingga 2 simpul yang berdampingan ( ada ruas menghubungkan ke dua simpul tersebut ) mempunyai warna

yang berbeda .Banyak warna yang dipergunkan , diminta seminimal mungkin.

Permasalahan :

Menentukan pola lampu lalulintas dengan jumlah fase minimal, dan pada setiap fase tidak ada perjalanan yang saling melintas . Perjalanan yang diperbolehkan adalah : A ke B, A ke C, A ke D, B ke C, B ke D, E ke B, E ke C dan E ke D

Setelah kita tahu jalur yang boleh dilewati kita akan menempuh langkah sebagai berikut

1. Membuat simpul sebagai simbol dari semua jalur yag diperboleh. letak masing-masing simpul bebas. lihat gambar berikut:

2. Menentukan ruas untuk menghubungkan 2 simpul yang saling melintas atau bersebrangan, pada gambar 1 diatas terlihat bahwa jalur AB, dan BD, saling berseberangan, maka kita hubungkan simpul AB dam BD dengan garis yang disebut ruas, dan kita akan memberikan ruas pada semua jalur yang bersebrangan, mari kita lihat gambar berikut:

3. pada gambar di atas kita telah menghubungkan semua jalur yang saling melintas, langkah berikutnya adalah memberikan warna pada masing-masing simpul yang terhubung dengan ruas atau garis, ketentuan pemberian warnanya adalah

• Gunakan Warna seminimal mungkin
• Simpul yang berdampingan atau /Terhubung langsung dengan ruas, tidak boleh berwarna sama
• Berikan warna yang sama pada simpul yang tidak terhubung secara langsung
• Simpul yang tidak terhubung dengan ruas atau simpul bebas, berarti lintasan tersebut boleh berlaku lampu hijau terus.
• Awal pewarnaan Bebas

Dari Gambar diatas, semua simpul telah diwarnai, dari gambar ersebut simpul EC berwarna kuning sendiri, hal ini dikarenakan simpul EC terhubung secara langsung dengan simpul AD yang berwarna merah, dan terhubung dengan simpul BD yang berwarna coklat, jadi kita harus memberi warna selain coklat dan merah, dalam hal ini kita pilih warna kuning, sementara simpul ED, AB, BC , jadi ke 3 simpul tersebut kita beri warna yang sama, selain merah, coklat dan kuning tentunya, pada contoh diatas kita beri warna hijau. Simpul ED, AB, BC adalah simpul bebas (simpul yang tidak terhubung dengan simpul lain) yang berarti jalur tersebut tidak ada jalur yang saling melintas artinya ketiga ruas bebas itu bisa berlaku lampu hijau terus.

4. langkah berikutnya adalah mengelompokan simpul berdasarkan warna
Merah => AC, AD
Coklat => BD, EB
Kuning => EC
Hijau => ED, AB, BC

Dari langkah-langkah diatas kita bisa mendapatkan 3 fase pola lampu lalu lintas sebagai berikut:

Hijau	AC, AD, ED, AB, BC
Merah	BD, EB, EC

Hijau	BD, EB, ED, AB, BC
Merah	AC,AD, EC

Hijau	EC, ED, AB, BC
Merah	AC,AD, BD, EB

Download Data Pewarnaan (Coloring) (Klik Disini)
Sekian pembahasan dari Pewarnaan (Coloring). Semoga bermamfaat dan terima kasih.

Read More

Metode Greedy

METODE GREEDY
Untuk mendapatkan solusi optimal dari permasalahan yg mempunyai dua kriteria yaitu Fungsi Tujuan/Utama & nilai pembatas (constrain).

Proses Kerja Metode Greedy :
Untuk menyeselesaikan suatu permasalahan dengan N input data yg terdiri dari beberapa fungsi pembatas & 1 fungsi tujuan yg diselesaikan dengan memilih beberapa solusi yg mungkin (feasible
solution/feasible sets), yaitu bila telah memenuhi fungsi tujuan/obyektif.

Metode GREEDY digunakan dlm penyelesaian
masalah - masalah :

1. Optimal On Tape Storage Problem
2. Knapsack Problem
3. Minimum Spanning Tree Problem
4. Shortest Path Problem.

Optimal Storage on Tapes Problem
-Bagaimana mengoptimalkan penyimpanan, agar data yang disimpan dapat termuat dengan optimal.
-Bagaimana susunan yang harus dibentuk

Proses pemecahannya

1.nilai panjang data (L), waktu penyimpanan (t) dan waktu rata-rata (MRT) jika ada

2.Tentukan urutan penyimpanan datanya

3.Hitung total penyimpanan ( jika ada kapasitas media penyimpanan maka totaltidak boleh melebihi)

4.Pilih total yang minimum (sesuai dengan unsur efisiensi dan efektifitas)

Contoh Sederhana :

Contohnya adalah pada kasus penukaran uang, misalkan kita memiliki uang senilai 32 dan akan kita tukarkan dengan koin, uang koin pecahan yang tersedia adalah 1, 5, 10, 25, jika kita mengharapkan agar pecahan yang kita miliki sedikit mungkin maka kita bisa menggunakan metode greedy dengan cara memilih pecahan terbesar terlebih dahulu. mari kita lihat

uang 32. pecahan 1,5,10,25 dengan metode greedy kita harus memilih pecahan terbesar terlebih dahulu yaitu 25, kemudian baru mengambil sampai sesuai dengan uang yang kita miliki. yaitu= 25+5+1+1=32(4 koin) sebenarnya ada beberapa alternatif solusi pemecahan masalah diatas sebagai berikut

32=1+1+1+1+…+1 (32 koin)
32=5+5+5+5+10+1+1 (7koin)
32=10+10+10+1+1 (5koin)

Dalam hal ini metode greedy berhasil mendapat kan hasil maksimal secara global atau secara keseluruhan dengan mengambil koin yang terbesar terlebih dahulu.

Namun ada kalanya metode greedy gagal mendapatkan solusi optimal, hal ini juga dikarenakan oleh sifat metode greedy itu sendiri yang memperhatikan keuntungan lokal(diawal) tanpa memperhatikan kemungkinan solusi yang lain, contoh:

Uang yang ditukar sebesar 7
Koin yang tersedia 5,4,3, dan 1

jika kita menukarkan uang tersebut dengan metode greedy maka kita harus mengambil pecahan terbesar lebih dulu yaitu 5, baru kemudian kita memilih pecahan berikutnya hingga genap berjumlah 7

7=5+1+1 (3koin)

alternatif solusi
7=4+3 (2koin)

pada contoh diatas jelas terlihat bahwa metode greedy gagal memberikan solusi optimal.

Untuk mata uang dollar AS, euro Eropa, dan crown Swedia, algoritma greedy selalu memberikan solusi optimum. Misalnya untuk menukarkan $6,39 dengan uang kertas (bill) dan koin sen (cent), kita dapat memilih:
•Satu buah uang kertas senilai $5
•Satu buah uang kertas senilai $1 ($5 + $1 = $6))
•Satu koin 25 sen ($5 + $1 + 25c = $6,25)
•Satu koin 10 sen ($5 + $1 + 25c + 10c = $6,35)
•Empat koin 1 sen ($5 + $1 + 25c + 10c + 1c + 1c + 1c + 1c = $6,39)

Contoh 1:

Diketahui 3 program yang akan disimpan dalam media penyimpanan dengan panjangmasing-masing 5, 10, dan 3. Bagaimana proses penyimpanan yang optimal denganmetode greedy.

Jawab

1.Tentukan nilai panjang, waktu, dan waktu rata-rata

Ada 3 program, dimisalkan panjangnya L1, L2, dan L3 dengan nilai L1=5, L2=10, danL3=3Waktu, disini tidak diketahui, berarti dianggap waktu tidak mempengaruhi prosespenyimpanan, berarti tidak ada waktu rata-rata.Berarti dalam kasus ini yang berpengaruh ha nya panjang dari setiap datanya.



2.Urutan penyimpanan dengan menggunakan teknik faktorial sesuai dengan jumlahdata.

Dari kasus diketahui jumlah data (n) adalah 3, berarti kombinasi yang dibutuhkanadalah n!, yaitu 3!=3*2*1 = 6. Jadi dibutuhkan 6 langkah dalam prosespenyusunannya.

No Order D(L)Total1 1,2,3 5+(5+10)+(5+10+3) 382 1,3,2 5+(5+3)+(5+3+10) 313 2,1,3 10+(10+5)+(10+5+3) 434 2,3,1 10+(10+3)+(10+3+5) 415 3,1,2 3+(3+5)+(3+5+10) 296 3,2,1 3+(3+10)+(3+10+5) 34Ket. No:1 : Order 1 = 5Order 1, 2 =5+10Order 1,2,3 = 5+10+3Jadi Total Order 1,2,3 = 5+(5+10)+(5+10+3)

3.Dari nilai di atas didapat nilai minimal adalah

a.Nilai terkecil pertama adalah 29, yaitu untuk posisi penyimpanan urutan ke-3 padaposisi pertama

b.Nilai terkecil kedua adalah 31, yaitu untuk posisi penyimpanan urutan ke-1 padaposisi pertama

c. Nilai terkecil ketiga bukan 34 dan 38, sebab urutan penyimpanan pada posisi ke-3dan ke-1 sudah diwakili oleh 29 dan 31, sehingga untuk urutan ketiga adalah 41.



Knapsack
1. Tentukan Fungsi Tujuan, yaitu mencari nilai maximum dari jumlah hasil perkalian antara nilai profit (Pi) dengan nilai probabilitas (Xi)
Maximum ∑Pi.Xi
2. Tentukan Fungsi Pembatas, yang merupakan hasil penjumlahan dari perkalian antara bobot (Wi) dengan nilai probabilitas (Xi) yang tidak boleh melebihi dari kapasitas media penyimpanan (M)
∑Wi.Xi≤M, dimana
0≤Xi≤1, Pi>0, Wi>0
Dari ke-2 cara di atas berarti kita harus mengetahui
1. Jumlah objek (n)
2. Bobot setiap objek (Wi)
3. Profit setiap objek (Pi)
4. Probabilitas setiap objek (Xi), dan
5. Kapasitas media penyimpanan (M)

Seperti penulis sudah sampaikan di atas bahwa permasalahan knapsack ini bisa diselesaikan dengan 3 cara, yaitu matematika, kriteria greedy dan algoritma greedy.
Penulis mencoba untuk membahas satu persatu.
1. Cara Matematika, kita harus memperhatikan nilai probabilitas dari setiap barang, karena nilai inilah sebagai penentunya dengan memperhatikan nilai probabilitas (Xi) yaitu 0≤Xi≤1. Disini nilai Xi kisarannya sangat banyak bisa 0, 0.1, 0.01, 0.001, …., 1.

2. Kriteria greedy dengan memperhatikan:
a. Pilih objek dengan nilai profit terbesar (Pi)
b. Pilih objek dengan bobot terkecil (Wi)
c. Pilih objek dengan nilai perbandingan profit dengan bobot yang terbesar (Pi/Wi)

3. Algortima greedy, yaitu
PROCEDURE GREEDY KNAPSACK (P, W, X, n)
REAL P(1:n), W(1:n), X(1:n), M, isi
INTEGER i, n
X(1:n) = 0
isi = M
FOR i = 1 TO n DO
IF W(i) > isi THEN EXIT ENDIF
X(i) = 1
isi = isi – W(i)
REPEAT
IF i ≤ n THEN X(i) = isi/W(i) ENDIF
END GREEDY KNAPSACK
Teknik yang ke-3 ini akan efektif jika objek disusun secara tidak naik (non increasing) berdasarkan nilai Pi/Wi.

Contoh :
Diketahui 3 barang yang akan disimpan pada suatu tempat yang memiliki kapasitas maksimal sebesar 20 Kg. Berat masing-masing barang adalah 18 Kg, 15 Kg, dan 10 Kg dimana setiap barang memiliki profit sebesar masing-masing 25, 24, dan 15. Tentukan barang mana saja yang dapat disimpan ke dalam tempat penyimpanan sehingga diperoleh nilai profit yang maksimal.
Jawab
1. Cara matematika
n = 3, (1, 2, 3)  objek
M = 20  kapasitas
(W1, W2, W3) = (18, 15, 10)
(P1, P2, P3) = (25, 24, 15)
Nilai probabilitas 0 ≤ Xi ≤ 1
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X1, X2, X3) (W1. X1) + (W2. X2) + (W3. X3) ≤ M (P1. X1) + (P2. X2) + (P3. X3)
1 (1, 2/15, 0) (18.1) + (15.2/15) + (10.0) ≤ 20 (25.1) + (24.2/15) + (15.0)
20 28,2
2 (1, 0, 1/5) (18.1) + (15.0) + (10.1/5) ≤ 20 (25.1) + (24.0) + (15.1/5)
20 28
3 (0, 1, ½) (18.0) + (15.1) + (10.1/2) ≤ 20 (25.0) + (24.1) + (15.1/2)
20 31,5
4 (1/3, ½, ½) (18.1/3) + (15.1/2) + (10.1/2) ≤ 20 (25.1/3) + (24.1/2) + (15.1/2)
18,5 27,83
… …. …. ….

Dengan cara ini sulit untuk menentukan yang paling optimal sebab kita harus mencari nilai probabilitas yang tersebar antara 0 dan 1, 0 ≤ Xi ≤ 1 untuk setiap objek. Cara ini disarankan tidak digunakan.
2. Cara kriteria greedy
n = 3, (1, 2, 3)  objek
M = 20  kapasitas
(W1, W2, W3) = (18, 15, 10)
(P1, P2, P3) = (25, 24, 15)
Nilai probabilitas 0 ≤ Xi ≤ 1
Kriteria greedy :
a. Pilih objek dengan nilai profit terbesar (Pi)
Susun data sesuai kriteria:
(P1, P2, P3) = (25, 24, 15)
(W1, W2, W3) = (18, 15, 10)
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X1, X2, X3) (W1. X1) + (W2. X2) + (W3. X3) ≤ M (P1. X1) + (P2. X2) + (P3. X3)
a (1, 2/15, 0) (18.1) + (15.2/15) + (10.0) ≤ 20 (25.1) + (24.2/15) + (15.0)
20 28,2
b. Pilih objek dengan bobot terkecil (Wi)
Susun data sesuai kriteria:
(P3, P2, P1) = (15, 24, 25)
(W3, W2, W1) = (10, 15, 18)
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X3, X2, X1) (W3. X3) + (W2. X2) + (W1. X1) ≤ M (P3. X3) + (P2. X2) + (P1. X1)
b (1, 2/3, 0) (10.1) + (15.2/3) + (18.0) ≤ 20 (15.1) + (24.2/3) + (25.0)
20 31

c. Pilih objek dengan nilai perbandingan profit dengan bobot yang terbesar (Pi/Wi)
Data yang diketahui:
(P1, P2, P3) = (25, 24, 15)
(W1, W2, W3) = (18, 15, 10)
perbandingan profit dengan bobot
P1/ W1 = 25/18 = 1,39
P2/ W2 = 24/15 = 1,6
P3/ W3 = 15/10 = 1,5
Susun data sesuai kriteria:
(P2, P3, P1) = (24, 15, 25)
(W2, W3, W1) = (15, 10, 18)

Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X2, X3, X1) (W2. X2) + (W3. X3) + (W1. X1) ≤ M (P2. X2) + (P3. X3) + (P1. X1)
c (1, 1/2, 0) (15.1) + (10.1/2) + (18.0) ≤ 20 (24.1) + (15.1/2) + (25.0)
20 31,5
Dari 3 kriteria di atas dapat disimpulkan bahwa fungsi tujuan yang bernilai maximum adalah 31,5 dengan fungsi pembatasnya adalah 20 dan nilai probabilitasnya adalah (X2, X3, X1) = (1, 1/2, 0), jadi disini yang memeberikan hasil optimal pada kriteria yang ke-3 yaitu Pilih objek dengan nilai perbandingan profit dengan bobot yang terbesar (Pi/Wi)
3. Cara algoritma greedy
Teknik ini akan efektif jika objek disusun secara tidak naik (non increasing) berdasarkan nilai Pi/Wi.
Data yang diketahui:
n = 3, (1, 2, 3)  objek
M = 20  kapasitas
(W1, W2, W3) = (18, 15, 10)
(P1, P2, P3) = (25, 24, 15)
Nilai probabilitas 0 ≤ Xi ≤ 1
perbandingan profit dengan bobot
P1/ W1 = 25/18 = 1,39
P2/ W2 = 24/15 = 1,6
P3/ W3 = 15/10 = 1,5
Susun data sesuai kriteria (non increasing):
(P2, P3, P1) = (24, 15, 25) atau
(P1, P2, P3) = (24, 15, 25)
(W2, W3, W1) = (15, 10, 18) atau
(W1, W2, W3) = (15, 10, 18)
Masukkan nilai kriteria di atas ke dalam algoritma greedy
1. PROCEDURE GREEDY KNAPSACK (P, W, X, n)  nama prosedur/proses
2. REAL P(1:n), W(1:n), X(1:n), M, isi  variabel yang digunakan
3. INTEGER i, n  variabel yang digunakan
4. X(1:n) = 0
5. isi = M
6. FOR i = 1 TO n DO
7. IF W(i) > isi THEN EXIT ENDIF
8. X(i) = 1
9. isi = isi – W(i)
10. REPEAT
11. IF i ≤ n THEN X(i) = isi/W(i) ENDIF
12. END GREEDY KNAPSACK  akhir prosedur/proses
Proses kegiatan dimulai dari langkah ke- 4 sampai dengan 11.
X(1:3) = 0, artinya X(1)=0, X(2)=0, X(3)=0
isi = M = 20
Pengulangan untuk i = 1 sampai dengan 3

Untuk i = 1
Apakah W(1) > isi
Apakah 15 > 20, jawabnya tidak, karena tidak maka perintah dibawah IF dikerjakan.
X(1) = 1  nilai probabilitas untuk objek pada urutan pertama (X1)
isi = 20 – 15 = 5
REPEAT  mengulang untuk perulangan FOR
Untuk i = 2
Apakah W(2) > isi
Apakah 15 > 5, jawabnya ya, karena ya maka perintah EXIT dikerjakan, yaitu keluar dari pengulangan/FOR dan mengerjakan perintah di bawah REPEAT.
Apakah 2 ≤ 3, jawabnya ya, karena ya maka X(2) = 5/10 = ½  nilai probabilitas untuk objek pada urutan kedua (X2).
Selesai (akhir dari prosedur greedy knapsack)
Berarti untuk nilai X(3) = 0 atau X3 = 0, sebab nilai probabilitas untuk objek ke-3 tidak pernah dicari.
Jadi
(P1, P2, P3) = (24, 15, 25)
(W1, W2, W3) = (15, 10, 18)
(X2, X3, X1) = (1, 1/2, 0)
Fungsi Pembatas :
∑ Wi.Xi ≤ M
(W1. X1) + (W2. X2) + (W3. X3) ≤ M
(15.1) + (10.1/2) + (18.0) ≤ 20
20 ≤ 20
Fungsi Tujuan :
∑ Pi.Xi = (P1. X1) + (P2. X2) + (P3. X3)
= (24.1) + (15.1/2) + (25.0)
= 31,5

PROBLEMA DAN MODEL GRAPH DALAM METODE
GREEDY ( Lanjutan )
1. TRAVELLING SALESMAN
Untuk menentukan waktu perjalanan seorang salesman seminimal mungkin.
Permasalahan:
Setiap minggu sekali, seorang petugas kantor telepon berkeliling untuk mengumpulkan coin-coin
pada telepon umum yang dipasang diberbagai tempat. Berangkat dari kantornya, ia mendatangi satu demi satu telepon umum tersebut dan akhirnya kembali ke kantor lagi. Masalahnya ia menginginkan suatu rute perjalanan dengan waktu minimal.

2. MINIMUM SPANNING TREE
Kasus MST Problem = m’cari min.biaya (cost) spanning tree dr setiap ruas (edge) graph yg m’btk pohon (tree).
Solusi dr p’masalah’ ini :
a. Dgn memilih ruas suatu graph yg memenuhi kriteria dr optimisasi yg m’hasilk’ biaya min.
b. Penambah’ dr setiap ruas pd seluruh ruas yg m’btk graph akan m’hasilk’ nilai/biaya yg kecil (minimum cost).
Kriteria2 dr spanning tree, yakni :
1. Setiap ruas pada graph harus terhubung (conected)
2. Setiap ruas pd graph hrs mpy nilai (label graph)
3. Setiap ruas pd graph tdk mpy arah (graph tdk berarah)

3. SHORTEST PATH PROBLEM
Permasalahan : menghitung jalur terpendek dr sbh graph berarah.
Kriteria utk permasalahan jalur terpendek/SP problem tsb :
1. Setiap ruas pd graph hrs mpy nilai (label graph)
2. Setiap ruas pd graph tdk hrs terhubung (unconnected)
3. Setiap ruas pd graph tsb hrs mempunyai arah (graph berarah).


Download Data Metode Greedy (Klik Disini)
Sekian pembahasan dari Metode Greedy. Semoga bermamfaat dan terima kasih.

Read More