PRAKTIKUM 13: Menerapkan algoritma greedy dalam pemrograman.

 IV. Alat/Bahan

• Komputer dengan lingkungan pemrograman C (misalnya, GCC atau Dev-C++).

• Editor teks untuk menulis kode C. Code::Blocks

• Compiler atau interpreter untuk menjalankan kode C.

• Buku atau materi referensi tentang pemrograman dalam bahasa C.

• .Modul 13 Menerapkan algoritma greedy dalam pemrograman.

V. Prosedur Praktikum

Praktekan Latihan Berikut:

Soal Praktek 1: Penjadwalan Tugas

1. Budi memiliki sejumlah tugas yang perlu diselesaikan dengan waktu mulai dan waktu selesai

tertentu, serta bobot atau keuntungan yang terkait dengan setiap tugas. Budi ingin

menggunakan algoritma greedy untuk menjadwalkan tugas-tugas tersebut sehingga

keuntungan total maksimum diperoleh. Implementasikan program dalam bahasa C yang dapat

menerima input tugas-tugas beserta waktu mulai, waktu selesai, dan bobotnya, dan

menampilkan urutan pelaksanaan tugas yang menghasilkan keuntungan total maksimum.

Soal Praktek 2: Penyelesaian Persamaan Linier

2. Andi ingin menyelesaikan sebuah persamaan linier dengan jumlah variabel dan persamaan

yang diberikan. Setiap persamaan memiliki koefisien variabel dan hasil yang diinginkan. Andi

ingin menggunakan algoritma greedy untuk mencari solusi yang memenuhi persamaan-

persamaan tersebut. Implementasikan program dalam bahasa C yang dapat menerima input

koefisien variabel, hasil, dan persamaan-persamaan, dan menampilkan solusi variabel yang

memenuhi persamaan-persamaan tersebut.

Soal Praktek 3: Penyelesaian Traveling Salesman Problem

3. Cindy adalah seorang sales yang ingin mengunjungi sejumlah kota untuk menjual produknya.

Setiap kota memiliki jarak yang terkait dengan kota lainnya. Cindy ingin menggunakan

algoritma greedy untuk menemukan rute perjalanan terpendek yang melintasi semua kota

sekali dan kembali ke kota awal. Implementasikan program dalam bahasa C yang dapat

menerima input jarak antar kota dan menampilkan rute perjalanan terpendek yang memenuhi

persyaratan tersebut.

Dalam menjawab soal-soal praktek tersebut, Anda perlu mengimplementasikan algoritma greedy

yang sesuai dengan masalah yang diberikan. Selain itu, pastikan juga untuk memperhatikan

masukan dari pengguna dan menampilkan hasil yang relevan sesuai dengan kebutuhan soal.

1. Jawaban Soal Praktek 1: Penjadwalan Tugas

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#include <stdio.h>

#include <stdlib.h>

typedef struct {

    int waktuMulai;

    int waktuSelesai;

    int bobot;

} Tugas;

int compare(const void *a, const void *b) {

    Tugas *tugasA = (Tugas *)a;

    Tugas *tugasB = (Tugas *)b;

    return tugasA->waktuSelesai - tugasB->waktuSelesai;

}

void jadwalTugas(Tugas tugas[], int n) {

    qsort(tugas, n, sizeof(Tugas), compare);

    int i, j;

    int *hasil = (int *)malloc(n * sizeof(int));

    hasil[0] = 0;

    j = 0;

    for (i = 1; i < n; i++) {

        if (tugas[i].waktuMulai >= tugas[j].waktuSelesai) {

            hasil[++j] = i;

        }

    }

    printf("Urutan Pelaksanaan Tugas: ");

    for (i = 0; i <= j; i++) {

        printf("%d ", hasil[i]);

    }

    printf("\n");

    int keuntunganTotal = 0;

    for (i = 0; i <= j; i++) {

        keuntunganTotal += tugas[hasil[i]].bobot;

    }

    printf("Keuntungan Total: %d\n", keuntunganTotal);

    free(hasil);

}

int main() {

    int n, i;

    printf("Masukkan jumlah tugas: ");

    scanf("%d", &n);

    Tugas *tugas = (Tugas *)malloc(n * sizeof(Tugas));

    printf("Masukkan waktu mulai, waktu selesai, dan bobot untuk setiap tugas:\n");

    for (i = 0; i < n; i++) {

        printf("Tugas %d: ", i + 1);

        scanf("%d %d %d", &tugas[i].waktuMulai, &tugas[i].waktuSelesai, &tugas[i].bobot);

    }

    jadwalTugas(tugas, n);

    free(tugas);

    return 0;

}

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

Program di atas meminta jumlah tugas dari pengguna dan meminta

input waktu mulai, waktu selesai, dan bobot untuk setiap tugas.

Program kemudian menggunakan algoritma greedy untuk menentukan

urutan pelaksanaan tugas yang menghasilkan keuntungan total

maksimum. Hasil urutan pelaksanaan tugas dan keuntungan total

kemudian ditampilkan.

2. Jawaban Soal Praktek 2: Penyelesaian Persamaan Linier

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#include <stdio.h>

#include <stdlib.h>

void cariSolusi(int n, int m, double koefisien[][n], double hasil[]) {

    double solusi[n];

    int i, j;

    for (i = 0; i < n; i++) {

        solusi[i] = 0.0;

    }

    for (i = 0; i < m; i++) {

        int variabelTerbesar = -1;

        double nilaiVariabelTerbesar = 0.0;

        for (j = 0; j < n; j++) {

            if (koefisien[i][j] > nilaiVariabelTerbesar) {

                nilaiVariabelTerbesar = koefisien[i][j];

                variabelTerbesar = j;

            }

        }

        solusi[variabelTerbesar] = hasil[i] / koefisien[i][variabelTerbesar];

        for (j = 0; j < m; j++) {

            if (koefisien[j][variabelTerbesar] != 0.0 && j != i) {

                double faktor = koefisien[j][variabelTerbesar] / koefisien[i][variabelTerbesar];

                for (int k = 0; k < n; k++) {

                    koefisien[j][k] -= faktor * koefisien[i][k];

                }

                hasil[j] -= faktor * hasil[i];

            }

        }

    }

    printf("Solusi Variabel:\n");

    for (i = 0; i < n; i++) {

        printf("x%d = %f\n", i + 1, solusi[i]);

    }

}

int main() {

    int n, m, i, j;

    printf("Masukkan jumlah variabel: ");

    scanf("%d", &n);

    printf("Masukkan jumlah persamaan: ");

    scanf("%d", &m);

    double koefisien[m][n];

    double hasil[m];

    printf("Masukkan koefisien variabel dan hasil untuk setiap persamaan:\n");

    for (i = 0; i < m; i++) {

        printf("Persamaan %d: ", i + 1);

        for (j = 0; j < n; j++) {

            scanf("%lf", &koefisien[i][j]);

        }

        scanf("%lf", &hasil[i]);

    }

    cariSolusi(n, m, koefisien, hasil);

    return 0;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

Program di atas meminta jumlah variabel dan jumlah persamaan

dari pengguna. Program kemudian meminta input koefisien

variabel dan hasil untuk setiap persamaan. Menggunakan

algoritma greedy, program mencari solusi variabel yang

memenuhi persamaan-persamaan tersebut. Solusi

variabeldidapatkan dengan mencari variabel dengan koefisien

terbesar pada setiap persamaan dan menghitung solusi variabel

tersebut. Kemudian, program melakukan update pada persamaan

lain dengan menggunakan solusi variabel yang telah ditemukan.

Hasil solusi variabel kemudian ditampilkan ke layar.

3. Jawaban Soal Praktek 3: Penyelesaian Traveling Salesman Problem

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#include <stdio.h>

#include <stdlib.h>

#define MAX 10

void temukanRuteTerpendek(int n, int jarak[MAX][MAX], int kotaAwal) {

    int rute[MAX];

    int kunjungan[MAX];

    int totalJarak = 0;

    int kunjunganTerakhir = kotaAwal;

    for (int i = 0; i < n; i++) {

        kunjungan[i] = 0;

        rute[i] = -1;

    }

    kunjungan[kotaAwal] = 1;

    rute[0] = kotaAwal;

    for (int i = 1; i < n; i++) {

        int jarakTerpendek = -1;

        int kotaTujuan = -1;

        for (int j = 0; j < n; j++) {

            if (kunjungan[j] == 0 && (jarakTerpendek == -1 || jarak[kunjunganTerakhir][j] < jarakTerpendek)) {

                jarakTerpendek = jarak[kunjunganTerakhir][j];

                kotaTujuan = j;

            }

        }

        kunjungan[kotaTujuan] = 1;

        rute[i] = kotaTujuan;

        totalJarak += jarakTerpendek;

        kunjunganTerakhir = kotaTujuan;

    }

    totalJarak += jarak[kunjunganTerakhir][kotaAwal];

    rute[n] = kotaAwal;

    printf("Rute Perjalanan Terpendek:\n");

    for (int i = 0; i <= n; i++) {

        printf("%d ", rute[i]);

    }

    printf("\nTotal Jarak: %d\n", totalJarak);

}

int main() {

    int n;

    int kotaAwal;

    printf("Masukkan jumlah kota: ");

    scanf("%d", &n);

    int jarak[MAX][MAX];

    printf("Masukkan jarak antar kota:\n");

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            scanf("%d", &jarak[i][j]);

        }

    }

    printf("Masukkan kota awal: ");

    scanf("%d", &kotaAwal);

    temukanRuteTerpendek(n, jarak, kotaAwal);

    return 0;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

Program di atas meminta jumlah kota dari pengguna dan meminta input jarak antar kota.

Menggunakan algoritma greedy, program menemukan rute perjalanan terpendek yang

melintasi semua kota sekali dan kembali ke kota awal yang ditentukan. Program

menampilkan rute perjalanan terpendek beserta total jarak yang ditempuh.

Dalam implementasi ini, digunakan matriks jarak antar kota untuk merepresentasikan graf.

Algoritma greedy memilih kota tujuan dengan jarak terpendek dari kunjungan terakhir pada

setiap iterasi. Setelah semua kota dikunjungi, kembali ke kota awal untuk menyelesaikan

rute perjalanan.

Jadi, program ini membantu Cindy untuk menemukan rute perjalanan terpendek dalam

sistem transportasi kota yang telah diberikan.

Soal Praktek: Optimasi Penjadwalan Produksi

4. Sebuah perusahaan manufaktur ingin mengoptimalkan penjadwalan produksinya

menggunakan algoritma greedy. Setiap produk memiliki waktu produksi yang telah ditentukan

dan keuntungan yang terkait dengan penjualan produk tersebut. Perusahaan ingin mencari

urutan produksi yang menghasilkan keuntungan total maksimum dengan mempertimbangkan

waktu produksi.

• Tugas Anda adalah membuat program dalam bahasa C yang menerima input waktu

produksi dan keuntungan setiap produk, dan menampilkan urutan produksi yang

menghasilkan keuntungan total maksimum.

• Tuliskan jawaban script dalam bahasa C dan jelaskan programnya dalam bahasa

Indonesia.

1. Jawaban Soal Praktek Optimasi Penjadwalan Produksi

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#include <stdio.h>

#include <stdlib.h>

typedef struct {

    int waktuProduksi;

    int keuntungan;

} Produk;

int pembanding(const void* a, const void* b) {

    Produk* produkA = (Produk*)a;

    Produk* produkB = (Produk*)b;

    double rasioA = (double)produkA->keuntungan / produkA->waktuProduksi;

    double rasioB = (double)produkB->keuntungan / produkB->waktuProduksi;

    if (rasioA < rasioB) {

        return 1;

    } else if (rasioA > rasioB) {

        return -1;

    } else {

        return 0;

    }

}

void jadwalProduksi(Produk produk[], int jumlahProduk) {

    qsort(produk, jumlahProduk, sizeof(Produk), pembanding);

    int totalWaktu = 0;

    int totalKeuntungan = 0;

    printf("Urutan produksi yang menghasilkan keuntungan total maksimum:\n");

    for (int i = 0; i < jumlahProduk; i++) {

        if (totalWaktu + produk[i].waktuProduksi <= 480) {

            printf("Produk %d (Waktu Produksi: %d menit, Keuntungan: Rp %d)\n", i + 1, produk[i].waktuProduksi, produk[i].keuntungan);

            totalWaktu += produk[i].waktuProduksi;

            totalKeuntungan += produk[i].keuntungan;

        }

    }

    printf("Keuntungan total: Rp %d\n", totalKeuntungan);

}

int main() {

    int jumlahProduk;

    printf("Masukkan jumlah produk: ");

    scanf("%d", &jumlahProduk);

    Produk produk[jumlahProduk];

    printf("Masukkan waktu produksi dan keuntungan untuk setiap produk:\n");

    for (int i = 0; i < jumlahProduk; i++) {

        printf("Produk %d:\n", i + 1);

        printf("Waktu Produksi: ");

        scanf("%d", &produk[i].waktuProduksi);

        printf("Keuntungan: ");

        scanf("%d", &produk[i].keuntungan);

    }

    jadwalProduksi(produk, jumlahProduk);

    return 0;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

Program di atas menggunakan algoritma greedy untuk mengoptimalkan penjadwalan

produksi. Setiap produk memiliki waktu produksi dan keuntungan yang telah ditentukan.

Program akan menerima input waktu produksi dan keuntungan untuk setiap produk,

kemudian menghitung urutan produksi yang menghasilkan keuntungan total maksimum

dengan mempertimbangkan waktu produksi. Produk diurutkan berdasarkan keuntungan per

unit waktu menggunakanalgoritma qsort. Selanjutnya, program akan mencetak urutan

produksi yang menghasilkan keuntungan total maksimum dan keuntungan total yang

diperoleh.

Dalam program ini, digunakan struktur data Produk untuk menyimpan informasi setiap

produk. Fungsi pembanding digunakan sebagai fungsi pembanding untuk pengurutan

produk berdasarkan keuntungan per unit waktu.

Fungsi jadwalProduksi digunakan untuk menentukan urutan produksi yang menghasilkan

keuntungan total maksimum. Pada fungsi ini, produk diurutkan menggunakan fungsi qsort

dengan menggunakan pembanding yang telah didefinisikan sebelumnya. Selanjutnya,

program akan memeriksa apakah waktu produksi masih memungkinkan untuk

menambahkan produk ke jadwal. Jika memungkinkan, produk akan ditambahkan ke jadwal

dan waktu produksi serta keuntungan akan diakumulasikan.

Di dalam fungsi main, program akan meminta input jumlah produk dan informasi waktu

produksi serta keuntungan untuk setiap produk. Kemudian, fungsi jadwalProduksi akan

dipanggil dengan argumen array produk dan jumlah produk yang diinputkan.

Output program akan menampilkan urutan produksi yang menghasilkan keuntungan total

maksimum beserta keuntungan total yang diperoleh.

Dengan menggunakan algoritma greedy, program ini dapat membantu perusahaan

manufaktur dalam mengoptimalkan penjadwalan produksinya untuk mendapatkan

keuntungan yang maksimum dengan mempertimbangkan waktu produksi.

VI. Analisa dan Kesimpulan

Algoritma greedy adalah pendekatan yang berguna dalam pemrograman untuk mencapai solusi

optimal secara lokal pada setiap langkah.

Mengimplementasikan algoritma greedy membutuhkan pemilihan opsi terbaik dengan

mempertimbangkan kriteria yang relevan.

Algoritma greedy dapat diterapkan dalam berbagai masalah optimasi di kehidupan sehari-hari.

Namun, perlu diingat bahwa algoritma greedy tidak selalu menghasilkan solusi global yang

optimal, karena fokusnya hanya pada langkah-langkah individu.

Oleh karena itu, sebelum menerapkan algoritma greedy, penting untuk memahami masalah secara

menyeluruh dan memeriksa apakah algoritma greedy cocok untuk masalah tersebut.