CODEWITHSUNDEEP
c++algorithmgreedy
Iberico
Iberico

Reputation: 182

Fractional Knapsack Algorithm segmentation fault

I am trying to solve the fractional knapsack problem by writing a function get_optimal_value which returns the total optimal value given the capacity of knapsack and weights and values of items. Over here in the function get_optimal_value, i am running into a segmentation fault problem on v_per_w[i] = values[i]/weights[i]; and i am not sure what is going on as i can't see where i have accessed foreign memory. This is my program. Help would be appreciated thanks :D

#include <iostream>
#include <vector>
#include <algorithm>

using std::vector;

double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
  double value = 0.0;
  vector<double> v_per_w = {};
  for (int i =0; i<weights.size(); ++i){
    v_per_w[i] = values[i]/weights[i]; //calculate v/w for the vector
  }

  //as long as capacity is not full
  while (capacity !=0){
    auto it = std::max_element(v_per_w.begin(), v_per_w.end()); //find max element in v/w
    auto it2 = find(v_per_w.begin(), v_per_w.end(), *it); // find the index of that max element in v/w
    int largest_index = it2 - v_per_w.begin(); 
    if (capacity>=weights[largest_index]){ 
      value+= values[largest_index]; //if capacity is more than the weight of that max v/w, add it all in
    }
    else{
      value += v_per_w[largest_index] * capacity; //else add whatever weight you can of that max v/w
    }
    values.erase(values.begin(), values.begin()+largest_index-1); //remove that item from all the vectors
    weights.erase(weights.begin(), weights.begin()+largest_index-1);
    v_per_w.erase(v_per_w.begin(), v_per_w.begin()+largest_index-1);
  }

  return value;
}

int main() {
  int n;
  int capacity;
  std::cin >> n >> capacity;
  vector<int> values(n);
  vector<int> weights(n);
  for (int i = 0; i < n; i++) {
    std::cin >> values[i] >> weights[i];
  }

  double optimal_value = get_optimal_value(capacity, weights, values);

  std::cout.precision(10);
  std::cout << optimal_value << std::endl;
  return 0;
}

Upvotes: 1

Views: 96

Answers (1)

Sam Varshavchik
Sam Varshavchik

Reputation: 118445

vector<double> v_per_w = {};

This creates a new vector, which is completely empty. It has no values. Immediately afterwards:

v_per_w[i] = values[i]/weights[i]; //calculate v/w for the vector

This attempts to change the existing values of v_per_w. However, since v_per_w is completely empty it has no values; this is a near-certain guarantee to produce the type of a crash you've observed. v_per_w[something] does not add new values to a vector. It modifies/accesses existing values in the vector, which must exist already.

Upvotes: 2

Related Questions