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