jeudi 26 mars 2020

How to solve the wrong output in rod cutting problem

int max_val(int l) {
  // input l
  int val[] = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
  if (l == 0)
    return 0;
  auto q = INT16_MIN;
  for (auto i = 0; i < l; i++) {
    q = std::max(q, val[i] + max_val(l - i - 1));
    std::cout << "  " << q;
    // ----->1
  }
  std::cout << " " << q;
  // ----->2
}

I tried this and at points 1 and 2 (marked with ----->) output is a very long number and I do not get the correct output when done in this way for all previous recursive problems. If I remove output q and return q at the end the code runs right.

The aim is to maximize value for given length of rod. Can anyone please explain what's wrong in this. The val is value array for each rod pieces i.e., 1 piece value 1, 2 pieces of value 5 etc till 10 and letter l is length of rod input. Thanks in advance.

Aucun commentaire:

Enregistrer un commentaire