Fractional Knapsack fringe cases

Question

I've been trying to solve the fractional knapsack problem as part of a greedy algorithm tutorial. The following snippet below is my code, and it seems to work for the basic cases, as I've tried running some basic tests such as having to choose two whole items, and then picking a fraction of a third item. However, when I input it into a testing suite, this algorithm always fails a test.

Failed case #6/13: Wrong answer got: 5810.101954463027 expected: 7777.731

I've been staring at the code trying to figure out where is the boundary cases where it has failed, and I've failed terribly at that, so I thought some fresh eyes would help. For reference, I'm adding an algorithm that actually passes the edge cases below mine.

My Algorithm (doesn't work)

double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
  double value = 0;
  vector<double> valuePerWeight;

  // Populating an array called valuePerWeight with ratios of value:weight
  for (int i=0; i < weights.size(); i++) {
    double valueWeightRatio = values[i]/weights[i];
    valuePerWeight.push_back(valueWeightRatio);
  }

  // While there are still items to choose, and the bag is not full
  while (weights.size() > 0 && capacity > 0) {
    double max;
    int itemNum;

    // Going through every item, find the item with the highest valuePerWeight and record it
    for (int i=0; i < weights.size(); i++) {
      if (valuePerWeight[i] > max) { // If an item has been found to have a valuePerWeight greater than the previous max, update the new max and item number
        max = valuePerWeight[i];
        itemNum = i;
      }
    }

    // If there is enough space in the knapsack to put the item with the highest valuePerWeight
    if (capacity >= weights[itemNum]) {
      capacity = capacity - weights[itemNum]; // Adding it to the bag, and updating the capacity and value
      value = value + values[itemNum];

      // Removing the item from the arrays to ensure that it doesn't get picked again
      weights.erase(weights.begin() + itemNum);
      values.erase(values.begin() + itemNum);
      valuePerWeight.erase(valuePerWeight.begin() + itemNum);
      max = 0;
      itemNum = 0;
    }

    // If there isn't enough space in the knapsack to put the whole item with highest valuePerWeight in
    else if (capacity < weights[itemNum]) {

      // Calculate what fraction of the item can be put in
      double fraction = (double)capacity / (double)weights[itemNum];

      // Put in that fraction of the item and update the capacity and value
      value = value + (double)fraction*values[itemNum];
      capacity = capacity - (double)fraction*weights[itemNum];

      return value;
    }
  }

  return value;
}

Algorithm that works

int get_max_index (vector<int> weights, vector<int> values) {
    int max_i = 0; // index of the item with the highest value:weight ratio
    double max = 0; // the max value:weight ratio we've seen so far

    for (int i = 0; i < weights.size(); i++) { // iterating through the weights
        if (weights[i] != 0 && (double)values[i]/weights[i] > max) { // if the weights are not 0 and the value:weight ratio we've seen is the highest so far
            max = (double)values[i]/weights[i]; // update the max value
            max_i = i; // capture the index of the item with the highest value:weight ratio
        }
    }
    return max_i;
}

double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
    double value = 0.0; // The answer to be returned, which is the value of the bag after putting all the items

    for (int i = 0; i < weights.size(); i++) { // Running this loop for every item in the bag
        if (capacity == 0) return value; // If the capacity of the bag has reached 0, return value
        int index = get_max_index(weights, values); // Get the index of the current item with the highest value:weight ratio
        int a = std::min(capacity, weights[index]); // Return the lower of the two: Remaining capacity of the bag or the weight of the item with the highest value:weight ratio
        value += a * (double)values[index]/weights[index]; // If there is sufficient capacity, put the whole item in, else, place a fraction of the item in: (capacity/weight)*value
        weights[index] -= a; // Update the item by removing it
        capacity -= a; // Update the capacity
    }

    return value;
}

Answer 1

I've found the problem!

I didn't cast the value as a double, and therefore in cases where the value:weight ratio differed by minuscule amounts, I got it wrong.

This change fixed the algorithm.

  // Populating an array called valuePerWeight with ratios of value:weight
  for (int i=0; i < weights.size(); i++) {
    double valueWeightRatio = (double)values[i]/weights[i];
    valuePerWeight.push_back(valueWeightRatio);
  }