Fractional Knapsack(Greedy)

Image Copyright: freeCodeCamp.org

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#include<bits/stdc++.h> #define MX 1000007 #define ll long long #define ull unsigned long long #define fori(a,n) for(int i=a;i<n;i++) #define forj(a,n) for(int j=0;j<n;j++) using namespace std; struct node { float w,p,u; }; bool com(node x,node y) { return x.u>y.u; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); /* 7 15 2 3 5 7 1 4 1 10 5 15 7 6 18 3 */ vector<node>v; int n,capacity; cin>>n>>capacity; int w[n],p[n]; fori(0,n) cin>>w[i]; fori(0,n){ cin>>p[i]; v.push_back({w[i],p[i],(float)p[i]/w[i]}); } sort(v.begin(),v.end(),com); int ans=0; fori(0,v.size()){ if(capacity>=v[i].w){ ans+=v[i].p; capacity-=v[i].w; } else{ ans+=(v[i].u*capacity); break; } } cout<<ans<<endl; return 0; }