fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. // Struktur untuk menyimpan data barang
  7. struct Item {
  8.     double value, weight;
  9. };
  10.  
  11. // Fungsi pembanding berdasarkan rasio nilai/bobot
  12. bool cmp(Item a, Item b) {
  13.     double r1 = a.value / a.weight;
  14.     double r2 = b.value / b.weight;
  15.     return r1 > r2;
  16. }
  17.  
  18. // Fungsi utama Fractional Knapsack
  19. double fractionalKnapsack(double capacity, vector<Item> items) {
  20.     // Urutkan berdasarkan rasio nilai per bobot
  21.     sort(items.begin(), items.end(), cmp);
  22.  
  23.     double totalValue = 0.0;
  24.  
  25.     for (auto &item : items) {
  26.         if (capacity <= 0) break;
  27.  
  28.         if (item.weight <= capacity) {
  29.             // Ambil seluruh barang
  30.             capacity -= item.weight;
  31.             totalValue += item.value;
  32.         } else {
  33.             // Ambil sebagian
  34.             totalValue += item.value * (capacity / item.weight);
  35.             capacity = 0;
  36.         }
  37.     }
  38.  
  39.     return totalValue;
  40. }
  41.  
  42. int main() {
  43.     cout << "=== Program Fractional (Rational) Knapsack ===\n";
  44.  
  45.     // Pengujian 1
  46.     vector<Item> items1 = { {60, 10}, {100, 20}, {120, 30} };
  47.     double capacity1 = 50;
  48.     cout << "\nUji 1:\n";
  49.     cout << "Kapasitas: " << capacity1 << endl;
  50.     cout << "Nilai maksimum: " << fractionalKnapsack(capacity1, items1) << endl;
  51.  
  52.     // Pengujian 2
  53.     vector<Item> items2 = { {5, 2}, {10, 3}, {15, 5}, {7, 7}, {8, 1} };
  54.     double capacity2 = 10;
  55.     cout << "\nUji 2:\n";
  56.     cout << "Kapasitas: " << capacity2 << endl;
  57.     cout << "Nilai maksimum: " << fractionalKnapsack(capacity2, items2) << endl;
  58.  
  59.     // Pengujian 3
  60.     vector<Item> items3 = { {4, 1}, {8, 2}, {15, 5}, {20, 10} };
  61.     double capacity3 = 8;
  62.     cout << "\nUji 3:\n";
  63.     cout << "Kapasitas: " << capacity3 << endl;
  64.     cout << "Nilai maksimum: " << fractionalKnapsack(capacity3, items3) << endl;
  65.  
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
=== Program Fractional (Rational) Knapsack ===

Uji 1:
Kapasitas: 50
Nilai maksimum: 240

Uji 2:
Kapasitas: 10
Nilai maksimum: 35.5

Uji 3:
Kapasitas: 8
Nilai maksimum: 27
https://ideone.com/v2OXBf
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!