Hi, I'm confused if it's possible to find exact one solution using backtrack algorithm?
Usually backtracking search the entire solution spaces.
I wonder if I can use it to find a feasible solution rather than search the entire solution space.
But I am stuck how to use when I should return from the recursive function stack?
Following is a backtracking algorithm to find the sum of array less < 13
And the result isCode:using namespace std; int array[] = { 8 , 15 , 2 , 3 }; bool choosen[4] = {0,0,0,0}; int best = 0; int cw = 0; int count(int idx) { return cw + array[idx-1]; } void print() { for (int i = 0; i != 4; ++i) cout << (choosen[i] ? 1: 0); cout << endl; } void backtrack(int i) { if (i > 4) { if (cw > best) best = cw; print(); } else { if (count(i) < 13) { cw = cw + array[i-1]; choosen[i-1] = true; backtrack(i+1); cw = cw - array[i-1]; choosen[i-1] = false; } backtrack(i+1); } } int main(void) { backtrack(1); cout << best << endl; return 0; }
1010
1001
1000
0100
0011
0010
0001
0000
11
I want to modify this to produce a solution of sum of array equation to 17
Which will produce one solution 0110 meaning that index[1] + index[2] == 17
Any advice is appreciated. Thx



LinkBack URL
About LinkBacks


