daily pastebin goal
33%
SHARE
TWEET

Untitled

a guest Jan 24th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // C/C++ program to solve fractional Knapsack Problem
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. // Struktura Item beleži težinu, cenu i inicijalnu poziciju svakog člana niza.
  7. // Zbog sortiranja unutar funkcije, permutovaće se redosled članova pa se neće
  8. // vratiti željena vrednost.
  9. struct Item
  10. {
  11.     int value, weight, position;
  12.  
  13.     // Konstruktor
  14.     Item(int value, int weight, int position)
  15.       : value(value), weight(weight), position(position) {}
  16. };
  17.  
  18. // Funkcija po kojoj se sortiraju članovi niza po opadajućem odnosu cene i težine
  19. bool cmp(struct Item a, struct Item b)
  20. {
  21.     double r1 = (double)a.value / a.weight;
  22.     double r2 = (double)b.value / b.weight;
  23.     return r1 > r2;
  24. }
  25.  
  26. // Vraća koji su  predmeti poneti, tako što rezultat predstavlja zbir
  27. // rednih broja predmeta stepenovanih na broj dva.
  28. // Npr. ako su korišćeni prvi, četvrti i sedmi predmet,
  29. // used_items = 2^1 + 2^4 + 2^7 - jedinstveno zapisujemo uzete predmete.
  30. double fractionalKnapsack(int weight, struct Item arr[], int n)
  31. {
  32.     // Sortiranje prvih n članova niza arr po funkciji cmp  
  33.     sort(arr, arr + n, cmp);
  34.  
  35.     int curWeight = 0; // Current weight in knapsack
  36.     double finalvalue = 0.0; // Result (value in Knapsack)
  37.  
  38.     // Prolazak kroz sve članove
  39.     for (int i = 0; i < n; i++)
  40.     {
  41.         // Ako dodavanje još jednog člana neće prekoračiti opseg,
  42.         // dodaj ga celog
  43.         if (curWeight + arr[i].weight <= weight)
  44.         {
  45.             curWeight += arr[i].weight;
  46.             finalvalue += arr[i].value;
  47.         }
  48.  
  49.         // Ako ne možemo dodati ceo član, dodaj njegov deo i izađi iz petlje.
  50.         else
  51.         {
  52.             int remain = weight - curWeight;
  53.             finalvalue += arr[i].value * ((double) remain / arr[i].weight);
  54.             break;
  55.         }
  56.     }
  57.  
  58.     // Returning final value
  59.     return finalvalue;
  60. }
  61.  
  62. // driver program to test above function
  63. int main()
  64. {
  65.     int W = 50; // Weight of knapsack
  66.     Item arr[] = {{60, 10}, {100, 20}, {120, 30}};
  67.  
  68.     int n = sizeof(arr) / sizeof(arr[0]);
  69.  
  70.     cout << "Maximum value we can obtain = "
  71.         << fractionalKnapsack(W, arr, n);
  72.     return 0;
  73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top