Solution: Fractional Knapsack Problem

#include "HelperFunctions.h"
double fractionalKnapsack(int knapsackWeight, struct Item itemArray[], int n) {
  int currentWeight = 0; // Current weight in knapsack 
  double finalvalue = 0.0; // Result (value in Knapsack) 
  double tempValue = 0.0;
  // compute all combinations
  int * combination = new int[n];
  for (int i = 0; i < n; i++) {
    combination[i] = i;
  }
  std::sort(combination, combination + n);
  
  // find value for all combinations
  do {
    for (int i = 0; i < n; i++) {
      // If adding Item won't overflow, add it completely 
      if (currentWeight + itemArray[combination[i]].weight <= knapsackWeight) {
        currentWeight += itemArray[combination[i]].weight;
        tempValue += itemArray[combination[i]].value;
      }
      // If we can't add current Item, add fractional part of it 
      else {
        int remain = knapsackWeight - currentWeight;
        tempValue += itemArray[combination[i]].value * ((double) remain / itemArray[combination[i]].weight);
      }
    }
    // save only the maximum value
    if (finalvalue < tempValue)
      finalvalue = tempValue;
    
    tempValue = 0.0;
    currentWeight = 0;
  } while (std::next_permutation(combination, combination + 3)); // produces all combinations
  delete combination;
  return finalvalue;
}
int main() {
  int knapsackWeight = 50;
  Item itemArray[] = {{120, 30}, {100, 20}, {60, 10}};
  int n = sizeof(itemArray) / sizeof(itemArray[0]);
  cout << "Maximum value we can obtain = ";
  cout << fractionalKnapsack(knapsackWeight, itemArray, n);
  return 0;
}