recursion problem help

[lock988]

Hi, this is part of a recursion problem and after very long, I still can't figure out why the output to the 2nd part of the qn is too large. Can anyone help? Thanks.

The qn is as follows: There are N warriors (N <= 20) each with an estimated strength. Some pair of warriors have conflict with one another and cannot be in the same army. Choose the strongest army from these warriors and output the max strength of the army (strength) and the no of ways to form an army of this strength (ways).

I created an array warrior[21] where warrior[i] store the strength of the ith warrior and fight[21][21] is a dimensional boolean array such that fight[x][y] return true if the xth and yth warrior cannot be in the same army. In the main program, I made a call to maxstrength(warrior,1,n,army,fight).

I declared strengths and ways as global variables initialised to 0.
army[i] is true if I decided to add warrior[i] to my army.

size is the actual no of warriors (n) in the input. it is less than 21. so I only use part of the array.

My recursive function is:

void  maxstrength(int arr[21],int i ,int size, bool army[21],bool  fight[21][21]){
    if (i  > size){
        int val = 0;
        for (int j=0;j<21;i++){
            if (army[j]){
                val += arr[j];}
        }
        if (val > strength){strength = val; ways =1;}
        else if (val == strength){ ways++; }
        return;
    }
    else {
        //dont choose
        maxstrength(arr,i+1,size,army,fight);
        //can choose?
        bool can_choose = true;
        for (int j=1;j<i;j++){
            if (army[j] && fight[j][i]){
                can_choose = false;
                break;
            }
        }
        if (can_choose)
            army[i] = true;
            maxstrength(arr,i+1,size,army,fight);
            army[i] = false;
        }
  
}

e.g.
warrior = [3,3,2,2,1] and the pair (1,2) and (4,5) have a conflict.
hence, the max strength should be 7 (warrior 1,3,4 or 2,3,4)
I obtained the correct strength (7) in the end but i got too many ways (6 instead of 2). What is the error? Does it has to do with global variables or did I pass the wrong parameters?

[TheIdeasMan]

Hi,

I am having trouble seeing where the base case (end condition) for the recursion is.

I thought it might have been (i > size) - size is 21? But you have a recursive call on line 14 which is directly after the else So this make it hard to understand what is happening.

Another confusing thing - you have 2 i variables, the first is an argument, the second is introduced on line and exists until line 7.

[lock988]

I just edited the question.
For convenience since the no of warriors,n, is <= 20, i created an array warrior of size 21. However, I only use part of it up to warriors[n].
So the base case is i(index) > size(n), which means I finish looking at the part of the array I am interested in.
I just changed the other i to a j.

[TheIdeasMan]

lock988 wrote:

So the base case is i(index) > size(n), which means I finish looking at the part of the array I am interested in.

TheIdeasMan wrote:

But you have a recursive call on line 14 which is directly after the else

So your base case disappears.

[lock988]

Hmm ...
The else block is supposed to break the problem into 2 cases 1) do not choose warrior i (the recursive call in line 14) 2) if it is possible, choose warrior i.
In both cases, I will increase the starting index in the next recursive call to i+1 so eventually it will be larger than size (as in the base case).

[TheIdeasMan]

break the problem into 2 cases 1) do not choose warrior i (the recursive call in line 14)

Ok, so why is the recursive call after the else ?

In both cases, I will increase the starting index in the next recursive call to i+1 so eventually it will be larger than size (as in the base case).

Right -oh I see that now - maybe you should make that clearer in the code. Put a comment to say what the end condition is, and also comment where it happens on line 10.

Good code should be self documenting in terms of variable and function names, and reading it should tell a story.

i and j are not good variable names, they look too similar, and in this case the i as the argument has meaning, so it should have a better name IMO