fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // Struktur dan Pembanding (Inti Greedy)
  5. typedef struct {
  6.     int v, w; 
  7.     double r; // Rasio v/w
  8. } Item;
  9.  
  10. int cmp(const void *a, const void *b) {
  11.     if (((Item *)b)->r > ((Item *)a)->r) return 1;
  12.     if (((Item *)b)->r < ((Item *)a)->r) return -1;
  13.     return 0;
  14. }
  15.  
  16. // Fungsi Solusi Knapsack
  17. double knapsack(Item items[], int n, int capacity, int *sisa) {
  18.     // 1. Hitung Rasio
  19.     for (int i = 0; i < n; i++) items[i].r = (double)items[i].v / items[i].w;
  20.  
  21.     // 2. Urutkan berdasarkan Rasio
  22.     qsort(items, n, sizeof(Item), cmp);
  23.  
  24.     double totalValue = 0.0;
  25.     int currentWeight = 0;
  26.  
  27.     // 3. Ambil Item
  28.     for (int i = 0; i < n; i++) {
  29.         if (currentWeight + items[i].w <= capacity) {
  30.             // Ambil Utuh
  31.             currentWeight += items[i].w;
  32.             totalValue += items[i].v;
  33.         } else {
  34.             // Ambil Sebagian (Fractional)
  35.             int remaining = capacity - currentWeight;
  36.             totalValue += items[i].v * ((double)remaining / items[i].w);
  37.             currentWeight = capacity; // Kapasitas penuh
  38.             break; 
  39.         }
  40.     }
  41.     *sisa = capacity - currentWeight;
  42.     return totalValue;
  43. }
  44.  
  45. int main() {
  46.     int n = 5;
  47.     int values[] = {5, 4, 7, 8, 10};
  48.     int weights[] = {10, 5, 7, 12, 8};
  49.     int capacity = 20;
  50.  
  51.     Item items[5];
  52.     for (int i = 0; i < n; i++) {
  53.         items[i].v = values[i];
  54.         items[i].w = weights[i];
  55.     }
  56.  
  57.     int sisa_kapasitas;
  58.     double optimalValue = knapsack(items, n, capacity, &sisa_kapasitas);
  59.  
  60.     // --- Hasil Uji Sesuai Permintaan ---
  61.     printf("Nilai Optimal: %.0lf\n", optimalValue);
  62.     printf("Sisa Kapasitas: %d\n", sisa_kapasitas);
  63.     printf("Keluaran Singkat (Nilai Sisa): **%.0lf %d**\n", optimalValue, sisa_kapasitas);
  64.  
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
5 4 7 8 10
10 5 7 12 8
20
stdout
copy 
Nilai Optimal: 21
Sisa Kapasitas: 0
Keluaran Singkat (Nilai Sisa): **21 0**
https://ideone.com/EuLe0w
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!