fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct item{
  5.     int weight;
  6.     int profit;
  7.     float u_profit;
  8. };
  9.  
  10. bool cmp(item a, item b){
  11.     return a.u_profit > b.u_profit;
  12. }
  13.  
  14. double profit = 0;
  15.  
  16. double fractional_knapsack(item items[], int n, int knapsack){
  17.  
  18.     sort(items, items+n, cmp);
  19.  
  20.  
  21.     for(int i = 0; i < n; i++){
  22.  
  23.         if(items[i].weight <= knapsack){
  24.             knapsack -= items[i].weight;
  25.             profit += items[i].profit;
  26.         }
  27.  
  28.         else{
  29.  
  30.             profit += (items[i].u_profit * knapsack);
  31.             knapsack = 0;
  32.             break;
  33.         }
  34.     }
  35.     return profit;
  36. }
  37.  
  38.  
  39. int main(){
  40.     int knapsack = 11;
  41.     int weight[] = {7, 5, 4, 3, 2};
  42.     int profit_arr[] = {15, 10, 20, 14, 12};
  43.     int n = sizeof(weight) / sizeof(weight[0]);
  44.     struct item items[5];
  45.  
  46.     for(int i = 0; i < n; i++){
  47.         items[i].weight = weight[i];
  48.         items[i].profit = profit_arr[i];
  49.  
  50.  
  51.         items[i].u_profit = (float)items[i].profit / items[i].weight;
  52.     }
  53.  
  54.     fractional_knapsack(items, n, knapsack);
  55.  
  56.  
  57.     cout << profit << endl;
  58.  
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
50.2857
https://ideone.com/Bt1Z3W
language:
C++14 (gcc 8.3)
created:
2 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!