-5

I'm trying to solve fractional knapsack problem, for now logic aside can anyone suggest me or explain me what is happening here? I never seen this runtime-error before, any help would be awesome, thank you.

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

using std::vector;
bool myfunction(int a, int b){return(a>b);}

double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
  double value = 0.0;
  vector<double> prop(weights.size());
  for(int i=0;i<=weights.size();i++){
      double Pvalue = (weights.at(i))/(values.at(i));
      prop.push_back(Pvalue);
  }
  std::sort(prop.begin(),prop.end(),myfunction);
  for(int it =0;it<=values.size();it++){
      while(capacity >=prop.at(it)){
          value+=prop.at(it);
          capacity-=prop.at(it);
      }
  }
  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;
}
MikeCAT
  • 73,922
  • 11
  • 45
  • 70
Sam Francis
  • 1
  • 2
  • 4
  • By the way, `(weights.at(i))/(values.at(i))` is doing integer division with truncation and will lead to getting wrong answer. – MikeCAT Aug 26 '20 at 22:48
  • In addition to the above if `values.at(i)` is 0, the program will likely crash. integer division by zero is usually immediately fatal. Might even be mandated to be immediately fatal by the C++ Standard, but I've never had cause to look it up and confirm it. – user4581301 Aug 26 '20 at 23:01
  • [Just looked it up](http://eel.is/c++draft/expr.mul#4) divide by zero is undefined behaviour. Most likely the CPU will raise an error that you can try to intercept and handle ([almost certainly futile](https://stackoverflow.com/questions/4747934/c-catch-a-divide-by-zero-error)) or outright kill the program, but it's [Undefined Behaviour](https://en.cppreference.com/w/cpp/language/ub) so you could get a plague of "Nasal Demons" instead. Note that you might not even get an error message saying it happened. The program may just seem to stop without giving you an answer. – user4581301 Aug 26 '20 at 23:09

2 Answers2

2

Suppose that v is a vector, only elements v[0] to v[v.size() - 1] are available and v[v.size()] is out-of-range.

Therefore,

for(int i=0;i<=weights.size();i++)

and

for(int it =0;it<=values.size();it++)

should be

for(int i=0;i<weights.size();i++)

and

for(int it =0;it<values.size();it++)

(use < instead of <=)

MikeCAT
  • 73,922
  • 11
  • 45
  • 70
  • 1
    In general `<=` in a `for` loop exit condition should be viewed with suspicion. It's not always wrong, but it is often enough to deserve a second or third glance to make sure it isn't. Then you probably want to document it so folks in the future won't waste time re-inspecting or worse, "Fix" the bug. – user4581301 Aug 26 '20 at 22:51
  • 1
    Yeah and if OP wants to read on it, "half open interval" is a good search – Jeffrey Aug 26 '20 at 22:54
  • By doing those i got rid of the error thankfully, but still the program is not yielding any o/p – Sam Francis Aug 26 '20 at 22:57
  • 1
    @SamFrancis The programmer's secret weapon is the debugger. With a debugger you can run a program on your terms and view what happens as it happens. If, while stepping through the program, you spot the program doing something you didn't expect, you probably found a bug. – user4581301 Aug 26 '20 at 22:59
1
for(int i=0;i<=weights.size();i++)

Will access the array one past the end of it. You need to use < weights.size() because c++ arrays are 0-based.

Jeffrey
  • 11,063
  • 1
  • 21
  • 42