fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. struct knap{
  6.     int object;
  7.     double PbW;
  8. };
  9.  
  10. bool comparePbW(knap n1,knap n2)
  11. {
  12.     if(n1.PbW > n2.PbW) return true;
  13.     else return false;
  14. }
  15.  
  16.  
  17.  
  18. int main()
  19. {
  20.     int n,m;
  21.     cin>>n>>m;
  22.     int profit[n];
  23.     int weight[n];
  24.     for(int i=0; i<n; i++)
  25.     {
  26.         cin>>profit[i];
  27.  
  28.     }
  29.     for(int i=0; i<n; i++)
  30.     {
  31.         cin>>weight[i];
  32.     }
  33.  
  34.     knap sack[n];
  35.     for(int i=0; i<n; i++)
  36.     {
  37.         sack[i].object=i;
  38.         sack[i].PbW = double(profit[i])/double(weight[i]);
  39.  
  40.     }
  41.     sort(sack, sack+n, comparePbW);
  42.  
  43.     int RW =m;
  44.     double X[n];
  45.     memset(X, 0.0, sizeof(X));
  46.     int i=0;
  47.     while(RW>0)
  48.     {
  49.         if(RW>=weight[sack[i].object])
  50.         {
  51.             X[sack[i].object] =1;
  52.             RW = RW - weight[sack[i].object];
  53.             i++;
  54.         }
  55.         else
  56.         {
  57.             X[sack[i].object] = double(RW)/double(weight[sack[i].object]);
  58.             RW = 0;
  59.         }
  60.     }
  61.  
  62.     for(int i=0; i<n; i++)
  63.     {
  64.         cout<<X[i]<<" ";
  65.     }
  66.     double maxprofit =0;
  67.     for(int i=0; i<n; i++)
  68.     {
  69.  
  70.         maxprofit = maxprofit +(X[i]*double(profit[i]));
  71.  
  72.     }
  73.     cout<<endl<<maxprofit<<endl;
  74.  
  75.  
  76.  
  77.  
  78.  
  79. }
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
1
2
10
42
11
stdout
copy 
0.047619 
0.47619
https://ideone.com/h51NTx
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!