Thread: Help with recursive algorithm

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    2

    Help with recursive algorithm

    I have to do a program that reads a list of positive numbers (5,3,6...) and a target. The program should find the target value (if posible) through combinations of sums and differences of the given number list. Also it should store in an array the combination of numbers and its sign. This is what I have:

    Code:
     void findobj(int j) 
    { 
        int i,temp; 
    
        i = 0; 
    
        do{ 
            i++; 
            if (numbers[i] != KEY) 
            { 
                   //the variable "sum" stores the sum of the combination numbers 
                sum+= numbers[i]; 
                 
            //stores solution numbers 
                solution[j] = numbers[i]; 
                temp = numbers[i]; 
    
               //KEY is a macro wich value is -1,  
              //it  prevents the program from selecting  
              //the same number twice 
                numbers[i] = KEY; 
                 
                if (j < N) 
                { 
                    findobj(j+1); 
                    numbers[i] = temp; 
    
                    if (sum != objetive) 
                    { 
                        sum-=numbers[i]; 
                        solution[j] =  -(numbers[i]); 
                         
                    } 
                } 
            } 
        }while ((i < N) && (sum != objetive)); 
    
        return; 
    }
    The problem is that the program doesnt find all the combinations, for example, given the following list (2,3,10,4,8) and target = 16, the variable sum never reaches the target, (the combination of numbers to reach the target is 2,10,4) but if the target = 15, the variable sum reaches the target.

    Thanks.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    So in other words you don't implement code to skip over numbers.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Aug 2006
    Posts
    11
    I tried to read the code, but I must admit I don't understand well how it works
    For instance, you use some variables defined elsewhere and not in the same function, numbers, solution, N, etc(I guess global variables)
    Also I see you use recursivity, but, you use it in a way hard to understand and prone to errors, instead to make the function returns some value, you make the function modify a global array. So it's not clear what is the END condition.
    You have here a problem of path finding, if I understood well, you have a list of numbers (n1,n2,n3..nN) and a target T, you have to sum them to get the final T (make combinations)
    There are algorithms to do that like the Tree Search (I guess the variant InDepth would fit for you)

    I would advise to review your algorithm more than try to tune this one.

    --------------------
    http://www.uberum.com

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I think this is known as the "backpack problem"; you might want to try googling it: http://www.google.ca/search?hl=en&q=...e+Search&meta=

    [edit] The first hit has a solution or two: http://www.edm2.com/0601/backpack.html [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    I believe this is actually called the 0-1 Knapsack problem. You can look up that along with recursion...but I think you'll probably just find dynamic programming solutions to that one.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 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
  2. recursive algorithm
    By vienne in forum C Programming
    Replies: 4
    Last Post: 07-18-2004, 06:03 PM
  3. Algorithm help (Changing from Recursive to Non Recursive)
    By Thantos in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2004, 07:27 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM