fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. // Struktur untuk merepresentasikan setiap item
  6. typedef struct {
  7.     int id;
  8.     int weight;
  9.     int value;
  10.     double ratio; // Rasio Nilai/Bobot
  11. } Item;
  12.  
  13. // Fungsi perbandingan untuk qsort
  14. // Digunakan untuk mengurutkan item berdasarkan rasio (descending/terbesar di awal)
  15. int compareItems(const void *a, const void *b) {
  16.     // Casting pointer void* ke pointer Item*
  17.     const Item *itemA = (const Item *)a;
  18.     const Item *itemB = (const Item *)b;
  19.  
  20.     // Untuk descending order, kita kembalikan (B - A).
  21.     if (itemA->ratio < itemB->ratio) return 1;
  22.     if (itemA->ratio > itemB->ratio) return -1;
  23.     return 0; // Rasio sama
  24. }
  25.  
  26. /**
  27.  * @brief Menyelesaikan masalah Rational Knapsack menggunakan strategi Greedy.
  28.  *
  29.  * @param items Array item.
  30.  * @param n Jumlah item.
  31.  * @param capacity Kapasitas maksimum knapsack.
  32.  * @return double Nilai total maksimum optimal.
  33.  */
  34. double rational_knapsack_greedy(Item items[], int n, int capacity) {
  35.  
  36.     // 1. Hitung rasio Nilai/Bobot untuk setiap item
  37.     for (int i = 0; i < n; i++) {
  38.         if (items[i].weight > 0) {
  39.             items[i].ratio = (double)items[i].value / items[i].weight;
  40.         } else {
  41.             items[i].ratio = 0.0;
  42.         }
  43.     }
  44.  
  45.     // 2. Urutkan item berdasarkan rasio menggunakan qsort
  46.     qsort(items, n, sizeof(Item), compareItems);
  47.  
  48.     double total_value = 0.0;
  49.     int current_weight = 0;
  50.  
  51.     printf("\n--- Proses Pengisian Knapsack (Greedy) ---\n");
  52.     printf("Item diurutkan berdasarkan Rasio (tertinggi ke terendah).\n");
  53.  
  54.     // 3. Iterasi dan ambil item
  55.     for (int i = 0; i < n; i++) {
  56.         if (current_weight >= capacity) {
  57.             break; // Knapsack sudah penuh
  58.         }
  59.  
  60.         int remaining_capacity = capacity - current_weight;
  61.  
  62.         if (items[i].weight <= remaining_capacity) {
  63.             // Kasus 1: Ambil seluruh item
  64.             current_weight += items[i].weight;
  65.             total_value += items[i].value;
  66.  
  67.             printf("Mengambil Item %d (Bobot %d, Nilai %d, Rasio %.2f) secara UTUH.\n", 
  68.                    items[i].id, items[i].weight, items[i].value, items[i].ratio);
  69.         } else {
  70.             // Kasus 2: Ambil sebagian (fraksi) dari item
  71.             double fraction = (double)remaining_capacity / items[i].weight;
  72.             double fractional_value = fraction * items[i].value;
  73.  
  74.             total_value += fractional_value;
  75.             current_weight = capacity; // Knapsack menjadi penuh
  76.  
  77.             printf("Mengambil Item %d (Bobot %d, Nilai %d, Rasio %.2f) dengan FRAKSI: %.2f%%.\n", 
  78.                    items[i].id, items[i].weight, items[i].value, items[i].ratio, fraction * 100);
  79.  
  80.             break; // Knapsack sudah penuh
  81.         }
  82.     }
  83.  
  84.     return total_value;
  85. }
  86.  
  87. // --- Fungsi utama untuk pengujian ---
  88. int main() {
  89.     printf("=== Uji Coba Rational Knapsack (Bahasa C) ===\n");
  90.  
  91.     // Data Uji
  92.     Item items[] = {
  93.         {1, 2, 10, 0.0}, // Rasio 5.0
  94.         {2, 4, 10, 0.0}, // Rasio 2.5
  95.         {3, 6, 12, 0.0}, // Rasio 2.0
  96.         {4, 9, 18, 0.0}  // Rasio 2.0
  97.     };
  98.     int n = sizeof(items) / sizeof(items[0]);
  99.     int capacity = 15;
  100.  
  101.     printf("Kapasitas Knapsack: %d kg\n", capacity);
  102.     printf("Daftar Item Awal:\nID | Bobot | Nilai\n");
  103.     printf("---|-------|-------\n");
  104.     for (int i = 0; i < n; i++) {
  105.         printf("%-2d | %-5d | %-5d\n", items[i].id, items[i].weight, items[i].value);
  106.     }
  107.  
  108.     // Panggil fungsi solusi
  109.     double result = rational_knapsack_greedy(items, n, capacity);
  110.  
  111.     // Tampilkan hasil dengan 2 angka di belakang koma
  112.     printf("\n--- Hasil Akhir ---\n");
  113.     printf("Nilai Maksimum Optimal: $%.2f\n", result);
  114.     printf("===========================================\n");
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5
5 4 7 8 10
10 5 7 12 8
20
stdout 
=== Uji Coba Rational Knapsack (Bahasa C) ===
Kapasitas Knapsack: 15 kg
Daftar Item Awal:
ID | Bobot | Nilai
---|-------|-------
1  | 2     | 10   
2  | 4     | 10   
3  | 6     | 12   
4  | 9     | 18   

--- Proses Pengisian Knapsack (Greedy) ---
Item diurutkan berdasarkan Rasio (tertinggi ke terendah).
Mengambil Item 1 (Bobot 2, Nilai 10, Rasio 5.00) secara UTUH.
Mengambil Item 2 (Bobot 4, Nilai 10, Rasio 2.50) secara UTUH.
Mengambil Item 3 (Bobot 6, Nilai 12, Rasio 2.00) secara UTUH.
Mengambil Item 4 (Bobot 9, Nilai 18, Rasio 2.00) dengan FRAKSI: 33.33%.

--- Hasil Akhir ---
Nilai Maksimum Optimal: $38.00
===========================================
https://ideone.com/103Q77
language:
C (gcc 8.3)
created:
3 hours 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!