Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // C/C++ program to solve fractional Knapsack Problem
- #include <bits/stdc++.h>
- using namespace std;
- // Struktura Item beleži težinu, cenu i inicijalnu poziciju svakog člana niza.
- // Zbog sortiranja unutar funkcije, permutovaće se redosled članova pa se neće
- // vratiti željena vrednost.
- struct Item
- {
- int value, weight, position;
- // Konstruktor
- Item(int value, int weight, int position)
- : value(value), weight(weight), position(position) {}
- };
- // Funkcija po kojoj se sortiraju članovi niza po opadajućem odnosu cene i težine
- bool cmp(struct Item a, struct Item b)
- {
- double r1 = (double)a.value / a.weight;
- double r2 = (double)b.value / b.weight;
- return r1 > r2;
- }
- // Vraća koji su predmeti poneti, tako što rezultat predstavlja zbir
- // rednih broja predmeta stepenovanih na broj dva.
- // Npr. ako su korišćeni prvi, četvrti i sedmi predmet,
- // used_items = 2^1 + 2^4 + 2^7 - jedinstveno zapisujemo uzete predmete.
- double fractionalKnapsack(int weight, struct Item arr[], int n)
- {
- // Sortiranje prvih n članova niza arr po funkciji cmp
- sort(arr, arr + n, cmp);
- int curWeight = 0; // Current weight in knapsack
- double finalvalue = 0.0; // Result (value in Knapsack)
- // Prolazak kroz sve članove
- for (int i = 0; i < n; i++)
- {
- // Ako dodavanje još jednog člana neće prekoračiti opseg,
- // dodaj ga celog
- if (curWeight + arr[i].weight <= weight)
- {
- curWeight += arr[i].weight;
- finalvalue += arr[i].value;
- }
- // Ako ne možemo dodati ceo član, dodaj njegov deo i izađi iz petlje.
- else
- {
- int remain = weight - curWeight;
- finalvalue += arr[i].value * ((double) remain / arr[i].weight);
- break;
- }
- }
- // Returning final value
- return finalvalue;
- }
- // driver program to test above function
- int main()
- {
- int W = 50; // Weight of knapsack
- Item arr[] = {{60, 10}, {100, 20}, {120, 30}};
- int n = sizeof(arr) / sizeof(arr[0]);
- cout << "Maximum value we can obtain = "
- << fractionalKnapsack(W, arr, n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement