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 - 54The result for this one should be:
50, 2, 2 - marked as true in ifChosen
20, 19, 15 - marked as false in ifChosenOf 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.
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.028sNow 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 1What I ask here is to help me change my recursion so it works faster, I did something like this it works much faster, but it gives me wrong results and I don't know how to fix it.
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;
}