Advertisement
wrench786

Lab task - Fractional Knapsack

Nov 4th, 2021
1,058
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define uom unordered_map
  6. #define pb push_back
  7. #define yes cout<<"YES\n"
  8. #define no cout<<"NO\n"
  9.  
  10. #define dot(x) fixed<<setprecision(x)
  11. #define wrench786 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  12.  
  13. #define PI (acos(-1.0))
  14. #define eps 0.00001
  15. const int LIMIT = 10000*100;
  16. const int mod = 1000000007;
  17. using namespace std;
  18.  
  19. bool cmp(pair<int,int>a, pair<int,int>b){
  20.     double x = (double)a.first/a.second;
  21.     double y = (double)b.first/b.second;
  22.  
  23.     if(x>=y)return true;
  24.     else return false;
  25. }
  26.  
  27. void solve(){
  28.     int capacity,n,i,j;
  29.     scanf("%d %d", &n, &capacity);
  30.     int price[n];
  31.     int weight[n];
  32.     vector<pair<int,int>>price_weight;
  33.  
  34.     for(i=0;i<n;i++){
  35.         scanf("%d",&price[i]);
  36.     }
  37.  
  38.     for(i=0;i<n;i++){
  39.         scanf("%d",&weight[i]);
  40.     }
  41.  
  42.     for(i=0;i<n;i++){
  43.         price_weight.pb(make_pair(price[i],weight[i]));
  44.     }
  45.  
  46.  
  47.     //sort(price_weight.begin(),price_weight.end(),cmp);
  48.  
  49.     for(i=0;i<n;i++){
  50.         for(j=i+1;j<n;j++){
  51.             if(cmp(price_weight[i],price_weight[j])){
  52.                 continue;
  53.             }
  54.             else{
  55.                 swap(price_weight[i],price_weight[j]);
  56.             }
  57.         }
  58.     }
  59.  
  60.     double ans_price=0.0;
  61.     double ans_weight=0.0;
  62.  
  63.     for(i=0;i<n;i++){
  64.         if(ans_weight<(double)capacity){
  65.             if(ans_weight+price_weight[i].second<=capacity){
  66.                 ans_weight+=price_weight[i].second;
  67.                 ans_price+=price_weight[i].first;
  68.                 cout<<"Taken weight = "<<price_weight[i].second<<endl;
  69.                 cout<<"Taken Price = "<<price_weight[i].first<<endl;
  70.             }
  71.             else{
  72.                 ans_price+= (price_weight[i].first *(capacity-ans_weight))/ (double)price_weight[i].second;
  73.                 ans_weight+= capacity-ans_weight;
  74.                 break;
  75.             }
  76.         }
  77.         else{
  78.             break;
  79.         }
  80.     }
  81.  
  82.     cout<<ans_price<<" "<<ans_weight<<endl;
  83.  
  84. }
  85.  
  86. int main(){
  87.     solve();
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement