fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // Struktur untuk merepresentasikan setiap barang
  5. typedef struct {
  6.     int id;           // Nomor identitas barang
  7.     float bobot;      // Bobot barang
  8.     float nilai;      // Nilai barang
  9.     float rasio;      // Rasio Nilai/Bobot (nilai/bobot)
  10. } Barang;
  11.  
  12. // Fungsi perbandingan untuk qsort. Mengurutkan barang berdasarkan Rasio secara MENURUN.
  13. int bandingkan_barang(const void *a, const void *b) {
  14.     Barang *barang_a = (Barang *)a;
  15.     Barang *barang_b = (Barang *)b;
  16.  
  17.     // Logika pengurutan menurun: jika rasio A < rasio B, A harus diletakkan setelah B (return 1).
  18.     if (barang_a->rasio < barang_b->rasio) {
  19.         return 1;
  20.     } else if (barang_a->rasio > barang_b->rasio) {
  21.         return -1;
  22.     } else {
  23.         return 0;
  24.     }
  25. }
  26.  
  27. // Fungsi utama untuk menyelesaikan masalah Rational Knapsack
  28. float knapsack_rational(Barang barang[], int jumlah_barang, float kapasitas_maks) {
  29.     // 1. Urutkan barang berdasarkan rasio Nilai/Bobot secara menurun (Strategi Greedy)
  30.     qsort(barang, jumlah_barang, sizeof(Barang), bandingkan_barang);
  31.  
  32.     float total_nilai = 0.0;
  33.     float sisa_kapasitas = kapasitas_maks;
  34.  
  35.     printf("--- Proses Pengambilan Barang Berdasarkan Rasio (Greedy) ---\n");
  36.     printf("| No. | Bobot | Nilai | Rasio | Sisa Kps | Aksi |\n");
  37.     printf("----------------------------------------------------------\n");
  38.  
  39.     // 2. Proses pengambilan barang
  40.     for (int i = 0; i < jumlah_barang; i++) {
  41.         if (sisa_kapasitas <= 0) {
  42.             break; // Ransel penuh, hentikan iterasi
  43.         }
  44.  
  45.         printf("| %-3d | %-5.1f | %-5.1f | %-5.2f | %-8.2f | ", 
  46.                barang[i].id, barang[i].bobot, barang[i].nilai, barang[i].rasio, sisa_kapasitas);
  47.  
  48.         if (barang[i].bobot <= sisa_kapasitas) {
  49.             // Ambil seluruh barang
  50.             total_nilai += barang[i].nilai;
  51.             sisa_kapasitas -= barang[i].bobot;
  52.             printf("Ambil SELURUH (Nilai +%.2f) |\n", barang[i].nilai);
  53.         } else {
  54.             // Ambil sebagian (fraksi) barang
  55.             float fraksi = sisa_kapasitas / barang[i].bobot;
  56.             float nilai_diambil = fraksi * barang[i].nilai;
  57.  
  58.             total_nilai += nilai_diambil;
  59.             sisa_kapasitas = 0; // Ransel terisi penuh oleh fraksi ini
  60.             printf("Ambil FRAKSI (%.2f) (Nilai +%.2f) |\n", fraksi, nilai_diambil);
  61.         }
  62.     }
  63.     printf("----------------------------------------------------------\n");
  64.  
  65.     return total_nilai;
  66. }
  67.  
  68. int main() {
  69.     // --- KASUS UJI (Contoh data, GANTI dengan data dari buku Anda) ---
  70.     // Barang-barang dengan Bobot (kg) dan Nilai (Rp)
  71.     float Bobot[] = {10.0, 20.0, 30.0};
  72.     float Nilai[] = {60.0, 100.0, 120.0};
  73.     float KAPASITAS_RANSEL = 50.0; 
  74.  
  75.     int JUMLAH_BARANG = sizeof(Bobot) / sizeof(Bobot[0]);
  76.  
  77.     // Inisialisasi dan pengisian data ke dalam array struktur Barang
  78.     Barang daftar_barang[JUMLAH_BARANG];
  79.     for (int i = 0; i < JUMLAH_BARANG; i++) {
  80.         daftar_barang[i].id = i + 1;
  81.         daftar_barang[i].bobot = Bobot[i];
  82.         daftar_barang[i].nilai = Nilai[i];
  83.         daftar_barang[i].rasio = Nilai[i] / Bobot[i];
  84.     }
  85.  
  86.     printf("--- Rasional Knapsack Problem (Informatika Kelas 11) ---\n");
  87.     printf("Kapasitas Ransel: %.2f kg\n\n", KAPASITAS_RANSEL);
  88.  
  89.     // Panggil fungsi utama Knapsack
  90.     float hasil_optimal = knapsack_rational(daftar_barang, JUMLAH_BARANG, KAPASITAS_RANSEL);
  91.  
  92.     printf("\n=============================================\n");
  93.     printf("NILAI TOTAL OPTIMAL yang dapat dicapai: Rp%.2f\n", hasil_optimal);
  94.     printf("=============================================\n");
  95.  
  96.     return 0;
  97. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
5
5 4 7 8 10
10 5 7 12 8
20
stdout
copy 
--- Rasional Knapsack Problem (Informatika Kelas 11) ---
Kapasitas Ransel: 50.00 kg

--- Proses Pengambilan Barang Berdasarkan Rasio (Greedy) ---
| No. | Bobot | Nilai | Rasio | Sisa Kps | Aksi |
----------------------------------------------------------
| 1   | 10.0  | 60.0  | 6.00  | 50.00    | Ambil SELURUH (Nilai +60.00) |
| 2   | 20.0  | 100.0 | 5.00  | 40.00    | Ambil SELURUH (Nilai +100.00) |
| 3   | 30.0  | 120.0 | 4.00  | 20.00    | Ambil FRAKSI (0.67) (Nilai +80.00) |
----------------------------------------------------------

=============================================
NILAI TOTAL OPTIMAL yang dapat dicapai: Rp240.00
=============================================
https://ideone.com/Cxb4WR
language:
C (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!