PRAKTIKUM 13.Menerapkan algoritma greedy dalam pemrograman.

Kumpulan Soal Praktikum Bahasa C

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.

Codingan:

#include <stdio.h> #include <stdlib.h> typedef struct { int waktuMulai; int waktuSelesai; int bobot; } Tugas; int compare(const void *a, const void *b) { return ((Tugas *)a)->waktuSelesai - ((Tugas *)b)->waktuSelesai; } void jadwalTugas(Tugas tugas[], int n) { qsort(tugas, n, sizeof(Tugas), compare); int i, j = 0; int *hasil = (int *)malloc(n * sizeof(int)); hasil[0] = 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; 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 (int 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; }

Hasil:

Output Program

Analisa Program:

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.

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.

Klik untuk melihat jawaban

Codingan:

#include <stdio.h> #include <stdlib.h> void cariSolusi(int n, int m, double koefisien[][n], double hasil[]) { double solusi[n]; for (int i = 0; i < n; i++) { solusi[i] = 0.0; } for (int i = 0; i < m; i++) { int variabelTerbesar = -1; double nilaiVariabelTerbesar = 0.0; for (int j = 0; j < n; j++) { if (koefisien[i][j] > nilaiVariabelTerbesar) { nilaiVariabelTerbesar = koefisien[i][j]; variabelTerbesar = j; } } solusi[variabelTerbesar] = hasil[i] / koefisien[i][variabelTerbesar]; for (int 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 (int i = 0; i < n; i++) { printf("x%d = %f\n", i + 1, solusi[i]); } } int main() { int n, m; 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 (int i = 0; i < m; i++) { printf("Persamaan %d: ", i + 1); for (int j = 0; j < n; j++) { scanf("%lf", &koefisien[i][j]); } scanf("%lf", &hasil[i]); } cariSolusi(n, m, koefisien, hasil); return 0; }

Hasil:

Output Program

Analisa Program:

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.

Soal Praktek 3: Penyelesaian Traveling Salesman Problem3. 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..

Klik untuk melihat jawaban

Codingan:

#include <stdio.h> #include <stdlib.h> #define MAX 10 void temukanRuteTerpendek(int n, int jarak[MAX][MAX], int kotaAwal) { int rute[MAX], kunjungan[MAX] = {0}, totalJarak = 0; int kunjunganTerakhir = kotaAwal; rute[0] = kotaAwal; kunjungan[kotaAwal] = 1; for (int i = 1; i < n; i++) { int jarakTerpendek = -1, 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, 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; }

Hasil:

Output Program

Analisa Program:

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.

Klik untuk melihat jawaban

Codingan:

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_SIZE 100 // Struktur Stack struct Stack { char data[MAX_SIZE]; int top; }; // Fungsi push: Menambahkan elemen ke dalam stack void push(struct Stack *stack, char element) { if (stack->top == MAX_SIZE - 1) { printf("Stack overflow, tidak dapat menambahkan elemen\n"); } else { stack->top++; stack->data[stack->top] = element; } } // Fungsi pop: Menghapus elemen teratas dari stack void pop(struct Stack *stack) { if (stack->top == -1) { printf("Stack underflow, tidak ada elemen yang dapat dihapus\n"); } else { stack->top--; } } // Fungsi peek: Mengambil nilai elemen teratas dari stack tanpa menghapusnya char peek(struct Stack stack) { if (stack.top == -1) { return '\0'; } else { return stack.data[stack.top]; } } // Fungsi isEmpty: Memeriksa apakah stack kosong int isEmpty(struct Stack stack) { return stack.top == -1; } // Fungsi isOperator: Memeriksa apakah karakter merupakan operator int isOperator(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/'; } // Fungsi precedence: Mengembalikan prioritas operator int precedence(char ch) { if (ch == '+' || ch == '-') return 1; else if (ch == '*' || ch == '/') return 2; return 0; } // Fungsi infixToPostfix: Mengubah notasi infix menjadi notasi postfix void infixToPostfix(char infix[], char postfix[]) { struct Stack stack; stack.top = -1; int i, j; for (i = 0, j = 0; i < strlen(infix); i++) { char ch = infix[i]; if (ch == ' ') continue; if (isdigit(ch) || isalpha(ch)) { postfix[j++] = ch; } else if (isOperator(ch)) { while (!isEmpty(stack) && precedence(peek(stack)) >= precedence(ch)) { postfix[j++] = peek(stack); pop(&stack); } push(&stack, ch); } else if (ch == '(') { push(&stack, ch); } else if (ch == ')') { while (!isEmpty(stack) && peek(stack) != '(') { postfix[j++] = peek(stack); pop(&stack); } pop(&stack); } } while (!isEmpty(stack)) { postfix[j++] = peek(stack); pop(&stack); } postfix[j] = '\0'; } int main() { char infix[MAX_SIZE]; char postfix[MAX_SIZE]; printf("Masukkan ekspresi infix: "); fgets(infix, sizeof(infix), stdin); // Menghapus karakter newline pada akhir ekspresi infix if (infix[strlen(infix) - 1] == '\n') { infix[strlen(infix) - 1] = '\0'; } infixToPostfix(infix, postfix); printf("Ekspresi postfix: %s\n", postfix); return 0; }

Hasil:

Output Program

Analisa Program:

"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"

Eka Kurniawan Zein

Program Studi: Teknologi Informasi

"Pengalaman adalah guru yang terbaik, hari ini harus lebih baik dari hari kemarin."

Dosen Pembimbing: Pak Totok Mulyono