Recursive backtracking

Question

I am having a problem with my backtracking function it loops with certain data I can't write here the whole program code but can put here my function.

bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen)
{

    if(moneyA == half)
        return true;
    else if(index >= quantity)
        return false;

    moneyA += values[index];

    if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
    {
        ifChosen[index] = true;
        return true;
    };

    moneyA -= values[index];

    if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
    {
        ifChosen[index] = false;
        return true;
    };

    return false;
}

Now here is the explanation:

quantity - number of elements in values array
values - array of numbers
index - variable to control the recursion
moneyA - variable that stores the sum of element from array values
half - number that moneyA should reach after recursion is done
ifChosen - array of boolean elements that refers to array values

The function gets quantity of elements which is lenght of values array, values an array with numbers in it's sorted from the highest to the lowest one, index controls recursion and default it's 0 so it starts from the first element, moneyA variable that stores numbers from the values array and it should reach half which is the half of numbers sumed from values array and ifChosen stores numbers that are chosen.

The whole function does this, it sums the elements from the values array and checks wether it reached the half if it's lower than half adds it to moneyA and mark it in ifChosen then it goes to next one, if the sum is higher than half it gets back and unmark it in ifChosen array and substract from moneyA. It should always get the highest elements.

Here is the simple example:

6 - number of elements
50, 20, 19, 15, 2, 2 - elements stored in values array
total sum is - 108
half of elements - 54

The result for this one should be:

50, 2, 2 - marked as true in ifChosen
20, 19, 15 - marked as false in ifChosen 

Of course for this simple example it does great job but for more complicated that have more numbers and one number occurs more than once it loops and recursion never stops. I've been actually working on this for 1.5 weeks and asked all my friends but nobody knows what is wrong with it. I know it has a bit to do with knapsack problem but I didn't have that one yet and still have to study.

I'm looking forward to any answer that could help.

I'm sorry for my punctuation but I'm here for the first time and didn't got used to formatting.

Here you got one example:

89 86 83 67 53 45 5 1    

44 43 34 33 33 24 23 23 23 22 21 21 19 12 11 9 8 7 5 3 2 2 2 1 1 1 1 1     

real    0m28.007s    

user    0m27.926s    

sys 0m0.028s

Now the one I think it loops forever: 43 elements:

12 2 2 1 3 4 5 6 7 89 33 12 45 23 44 23 11 44 1 3 5 7 88 33 8 19 43 22 86 5 34 23 21 67 83 24 21 53 9 11 34 1 1

@Karl Bielefeldt Yes I know that there are so many combinations that's why I am trying to speed it up. For now this is all I got but it gives me wrong results for certain input. Can anyone make that correct, it works much faster than before ?

bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen){

if(index>=quantity && moneyA == half){ return true;}
else if(index>=quantity) return false;

moneyA+=values[index];
ifChosen[index]=true;

if(moneyA<=half){       
    shareMoney(quantity,values,index+1,moneyA, half,ifChosen);
    if(moneyA==half) return true;

    return true;
}else{
    shareMoney(quantity,values,index+1,moneyA, half,ifChosen);      
    moneyA-=values[index];
    ifChosen[index]=false;

    return true;
}


return false;}

Answer 1

The typical way to cut down on the number of iterations on a problem like this is to calculate a bound on a subtree by solving a linear program (like your problem, but the remaining variables are allowed to take on fractional values). Simplex solves the linear program in approximately quadratic time instead of exponential. The best solution for the linear program is at least as good as the best integer or binary solution with the same constraints, so if the linear solution is worse that your current best, you can throw away the whole subtree without exhaustive evaluation.

EDIT: Let's start by simplifying the brute force algorithm:

int* shareMoney( int pool_size, int *pool, int *solution, int cumsum, int goal)
{
    if (cumsum == goal) return solution;
#if PRUNE_ABOVE
    if (cumsum > goal) return 0;
#endif
    if (!pool_size) return 0;

#if PRUNE_BELOW
    int max = cumsum;
    for( int n = pool_size; n--; max += pool[n] );
    if (max < goal) return 0;
#endif

    int* subproblem = shareMoney(pool_size-1, pool+1, solution, cumsum, goal);
    if (subproblem) return subproblem;

    *solution = *pool;
    return shareMoney(pool_size-1, pool+1, solution+1, cumsum+*pool, goal);
}

After execution, solution contains a list of the values used to reach the goal, and the returned pointer indicates the end of the list.

The conditional blocks are my first suggested improvement. No recursion is necessary in these cases.

We can eliminate the need to iterate to calculate max at each step:

int* shareMoney( int pool_size, int *pool, int *solution, int cumsum, int poolsum, int goal)
{
    if (cumsum == goal) return solution;
#if PRUNE_ABOVE
    if (cumsum > goal) return 0;
#endif
    if (!pool_size) return 0;

#if PRUNE_BELOW
    if (cumsum + poolsum < goal) return 0;
#endif

    int* subproblem = shareMoney(pool_size-1, pool+1, solution, cumsum, poolsum - *pool, goal);
    if (subproblem) return subproblem;

    *solution = *pool;
    return shareMoney(pool_size-1, pool+1, solution+1, cumsum+*pool, poolsum - *pool, goal);
}

Here's a function to solve the integer version (better for repeated coin denominations):

int* shareMoney( int pool_size, int *pool_denom, int *pool_cardinality, int *solution, int cumsum, int poolsum, int goal)
{
    if (cumsum == goal) return solution;
#if PRUNE_ABOVE
    if (cumsum > goal) return 0;
#endif
    if (!pool_size) return 0;

#if PRUNE_BELOW
    if (cumsum + poolsum < goal) return 0;
#endif

    poolsum -= *pool_cardinality * *pool_denom;
    for (*solution = *pool_cardinality; *solution >= 0; --*solution) {
        int* subproblem = shareMoney(pool_size-1, pool_denom+1, pool_cardinality+1, solution+1, cumsum + *solution * *pool_denom, poolsum, goal);
        if (subproblem) return subproblem;
    }

    return 0;
}

Instead of getting a straight list of individual coins, it takes a list of denominations, and the number of available coins of each one. The result is the number of coins of each denomination needed by the solution.