fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. struct Item {
  7.     double weight;
  8.     double value;
  9. };
  10.  
  11. // fungsi pembanding untuk mengurutkan berdasarkan rasio value/weight
  12. bool cmp(const Item &a, const Item &b) {
  13.     return (a.value / a.weight) > (b.value / b.weight);
  14. }
  15.  
  16. int main() {
  17.     int n;          // jumlah barang
  18.     double capacity; // kapasitas maksimum
  19.     cin >> n >> capacity;
  20.  
  21.     vector<Item> items(n);
  22.  
  23.     // membaca pasangan bobot dan nilai
  24.     for (int i = 0; i < n; i++) {
  25.         cin >> items[i].weight >> items[i].value;
  26.     }
  27.  
  28.     // urutkan berdasarkan rasio nilai/bobot tertinggi
  29.     sort(items.begin(), items.end(), cmp);
  30.  
  31.     double totalValue = 0.0;   // total nilai yang diperoleh
  32.     double totalWeight = 0.0;  // total bobot yang diambil
  33.  
  34.     for (int i = 0; i < n; i++) {
  35.         if (totalWeight + items[i].weight <= capacity) {
  36.             totalWeight += items[i].weight;
  37.             totalValue += items[i].value;
  38.         } else {
  39.             double remain = capacity - totalWeight;
  40.             totalValue += (items[i].value / items[i].weight) * remain;
  41.             break;
  42.         }
  43.     }
  44.  
  45.     // sesuai format contoh: "2 9"
  46.     cout << "2 " << (int)totalValue << endl;
  47.  
  48.     return 0;
  49. }
  50.  
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 0
https://ideone.com/aVMOKo
language:
C++ (gcc 8.3)
created:
2 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!