#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> p;
vector<p>v;
bool compare(p A, p B)
{
return A.second * B.first > B.second * A.first;
}
void fractional_knapsack()
{
int n, value, weight, want_weight, i;
cout << "Enter Array Size :: ";
cin >> n;
cout << "Enter Weight and Value :: " << endl;
for(i=1;i<=n;i++)
{
cin >> weight >> value;
v.push_back(p(weight, value));
}
sort(v.begin(), v.end(), compare);
cout << "Total Weight :: ";
cin >> want_weight;
double ans = 0;
for(i=0;i<n;i++)
{
int z = min(want_weight, v[i].first);
want_weight = want_weight - z;
ans = ans + z*(double)(v[i].second/v[i].first);
}
cout << "Maximum Cost :: " << ans << endl;
}
int main()
{
fractional_knapsack();
return 0;
}
using namespace std;
typedef pair<int, int> p;
vector<p>v;
bool compare(p A, p B)
{
return A.second * B.first > B.second * A.first;
}
void fractional_knapsack()
{
int n, value, weight, want_weight, i;
cout << "Enter Array Size :: ";
cin >> n;
cout << "Enter Weight and Value :: " << endl;
for(i=1;i<=n;i++)
{
cin >> weight >> value;
v.push_back(p(weight, value));
}
sort(v.begin(), v.end(), compare);
cout << "Total Weight :: ";
cin >> want_weight;
double ans = 0;
for(i=0;i<n;i++)
{
int z = min(want_weight, v[i].first);
want_weight = want_weight - z;
ans = ans + z*(double)(v[i].second/v[i].first);
}
cout << "Maximum Cost :: " << ans << endl;
}
int main()
{
fractional_knapsack();
return 0;
}
Comments
Post a Comment