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