Backtracking algorithm??

This is a discussion on Backtracking algorithm?? within the C++ Programming forums, part of the General Programming Boards category; Hi, I'm confused if it's possible to find exact one solution using backtrack algorithm? Usually backtracking search the entire solution ...

  1. #1
    Registered User
    Join Date
    Feb 2010
    Posts
    32

    Backtracking algorithm??

    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
    Code:
    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;
    }
    And the result is
    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
    Last edited by ovid; 08-15-2010 at 12:40 AM.

  2. #2
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    Why not just modify it by adding an additional check that checks if it is the solution you are looking for? If that function returns true, return prematurely.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 06:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21