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. // Comparator for sorting items by unit profit in descending order
  11. bool cmp(item a, item b){
  12.     return a.u_profit > b.u_profit;
  13. }
  14.  
  15. // Global variable 'profit' is slightly unconventional but works with the current setup
  16. double profit = 0; 
  17.  
  18. double fractional_knapsack(item items[], int n, int knapsack){
  19.     // 1. Sort items based on the unit profit (greedy choice)
  20.     sort(items, items+n, cmp);
  21.  
  22.     // 2. Iterate and fill the knapsack
  23.     for(int i = 0; i < n; i++){
  24.         // If the entire item fits
  25.         if(items[i].weight <= knapsack){
  26.             knapsack -= items[i].weight;
  27.             profit += items[i].profit;
  28.         }
  29.         // If only a fraction of the item fits
  30.         else{
  31.             // Add the profit of the fractional part (unit_profit * remaining_capacity)
  32.             profit += (items[i].u_profit * knapsack);
  33.             knapsack = 0; // Knapsack is now full
  34.             break;       // Stop the process
  35.         }
  36.     }
  37.     return profit;
  38. }
  39.  
  40.  
  41. int main(){
  42.     int knapsack = 11;
  43.     int weight[] = {7, 5, 4, 3, 2};
  44.     int profit_arr[] = {15, 10, 20, 14, 12}; // Renamed to avoid confusion with global 'profit'
  45.     int n = sizeof(weight) / sizeof(weight[0]);
  46.     struct item items[5];
  47.  
  48.     for(int i = 0; i < n; i++){
  49.         items[i].weight = weight[i];
  50.         items[i].profit = profit_arr[i];
  51.  
  52.         // FIX: Cast 'profit' to (float) to force floating-point division
  53.         items[i].u_profit = (float)items[i].profit / items[i].weight; 
  54.     }
  55.  
  56.     fractional_knapsack(items, n, knapsack);
  57.  
  58.     // Output the final computed profit
  59.     cout << profit << endl; 
  60.  
  61.     return 0; // Added return 0 for good practice
  62. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
50.2857
https://ideone.com/gcbXhX
language:
C++ (gcc 8.3)
created:
1 day 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!