Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    New to the CF scene
    Join Date
    Sep 2010
    Posts
    8
    Thanks
    1
    Thanked 0 Times in 0 Posts

    using backtracking to print all possible orders of numbers

    hi there,
    i've started working on the knapsack problem. i have an array of a given number of items, the robber can only steal up to a limited weight. so i thought i would create an array of the same length that holds only '1' or '0'. 1-stolen, 0-left.
    the method i have here is supposed to print all possible combinations of '0' and '1' in the length of the array of items. if there are 2 items that can be stolen i would create an array of 2 that will hold these numbers:
    00
    01
    10
    11
    which represents all the possible cases
    so here's my code
    PHP Code:
    public class Backtracking {

        
    //this method prints all the possible combinations of the digits '1' and '0'
        //in a given number of digits (which is order.length)
        //@param order - the given array of int. for now only its size matters
        //@param index - the method will work on order[index]
        //@param newValuse - either '1' or '0'
        
    private static void orders(int[] orderint indexint newValue) {
            if (
    index==order.length) {
                
    //when the number of digits in the current number
                //reaches order.length print it i.e. if order.length is 3
                //and we have '000' or '001' print it
                
    System.out.println("entered end condition");
                for (
    int i=0i<=index-1i++) {
                
    System.out.print(order[i]+" ");
                }
                
    System.out.println();
            }
            else {
                
    System.out.println("entered recursion at index "+index);
                
    System.out.println("input "+newValue);
                
    order[index]=newValue;
                
    index+=1;
                
    orders(orderindex0);
                
    System.out.println("changing value to 1 at index "+index);
                
    orders(orderindex1);
            }
        }
        public static 
    void main (String[] args) {
            
    int[] weights = {3,3};
            
    orders(weights00);

        }


    it doesn't give me all possible combinations. if i called the method from main using the parameter newValue=0 it will only print the numbers starting with 0.
    also it prints everything twice
    here's my output:
    PHP Code:
    entered recursion at index 0
    input 0
    entered recursion at index 1
    input 0
    entered end condition
    0 0 
    changing value to 1 at index 2
    entered end condition
    0 0 
    changing value to 1 at index 1
    entered recursion at index 1
    input 1
    entered end condition
    0 1 
    changing value to 1 at index 2
    entered end condition
    0 1 
    hope i was clear enough
    how can i make it right? thank you!

  • #2
    Regular Coder
    Join Date
    Feb 2008
    Location
    Edinburgh - Scotland
    Posts
    107
    Thanks
    0
    Thanked 12 Times in 12 Posts
    Hmm I dont think your recursion is correct - I found this example which I feel you should perhaps study - click the link and have a read of the BackKnap.rtf link which is basically a Java implementation of what you want to do - try running it - if it operates as you want, split it apart and figure out where your code differs to theirs!


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •