I'm getting a segmentation fault in the following code for a greedy algorithm for the knapsack problem. I've never successfully solved a segmentation fault before, though I've seen them, so I'd appreciate some help.
The message I get when I run the debugger is that there is no "malloc.c". When I run valgrind, I get an "Invalid read of size 4". Between that and the nature of the bug, I'm guessing I'm trying to access a vector element that is nonexistant. But I've tried every way I could think of to try and make sure that the loop didn't overstep its bounds when iterating through the vector.
(I've done this without using a C++11 range-based for loop and still get the same error. It doesn't seem to matter what I choose for the parameters of the for loop, it still throws a segmentation error.)
Thanks in advance.
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
using namespace std;
bool decreaseSort(int a, int b)
{
return a > b; //sort by decreasing value for better performance
}
double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
sort(weights.begin(),weights.end(), decreaseSort);
sort(values.begin(),weights.end(), decreaseSort);
vector<int> ourKnapsack(values.size(), 0);
double totalValue = 0.0;
int ourInput = 0;
for (auto i : ourKnapsack){
int ourValue = values.at(i);
int ourWeight = weights.at(i);
double unitValue = (double)ourValue/ourWeight;
if (capacity == 0)
return totalValue;
if (weights.at(i) < capacity){
ourInput = weights.at(i);
}
else {
ourInput = capacity;
}
totalValue = totalValue * (ourInput * unitValue);
weights.at(i)-=ourInput;
ourKnapsack.at(i)+=ourInput;
capacity-=ourInput;
}
return totalValue;
}
int main() {
int n = 3;
int capacity = 50;
vector<int> values(n);
values = {60,100,120};
vector<int> weights(n);
weights = {20,50,30};
double optimal_value = get_optimal_value(capacity, weights, values);
std::cout.precision(10);
std::cout << optimal_value << std::endl;
return 0;
}
Aucun commentaire:
Enregistrer un commentaire