Results 1 to 7 of 7
  1. #1
    yotamoo is offline Member
    Join Date
    Sep 2010
    Posts
    4
    Rep Power
    0

    Default 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[] order, int index, int 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=0; i<=index-1; i++) {
    			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(order, index, 0);
    			System.out.println("changing value to 1 at index "+index);
    			orders(order, index, 1);
    		}
    	}
    	public static void main (String[] args) {
    		int[] weights = {3,3};
    		orders(weights, 0, 0);
    
    	}
    
    }
    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. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    Also posted at coding forums.

  3. #3
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

  4. #4
    yotamoo is offline Member
    Join Date
    Sep 2010
    Posts
    4
    Rep Power
    0

    Default

    well, i didn't know it is the same forum. still, any ideas?

  5. #5
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,385
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by yotamoo View Post
    well, i didn't know it is the same forum. still, any ideas?
    Yes, don't enumerate all possibilities; given a knapsack problem NSP and a given item I with weight w and value v the best solution for the NSP is one of NSP-I or NSP, i.e. you either take item I or you don't. If you take item I your knapsack can still carry W-w where W is the weight of the empty knapsack and the total value is V(NSP-I)+v, i.e. the value of the reduced knapsack problem plus the value of I (because you took that item). Otherwise, (you didn't take item I) the value is simply V(NSP). Perform this step for all possible items I and quit iterating when there is no room anymore for any item in the knapsack (order the items according to their weight w).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    i didn't know it is the same forum

    The point is more that it isn't the same forum. Because of that many involved in the discussion will be quite unaware of the rest of that discussion. It is a good idea to follow the advice given at JavaRanch and let people at both forums know about the other (ie provide a link from one part of the dicussion to the other).

  7. #7
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

Similar Threads

  1. need help with backtracking
    By Dumisan in forum Advanced Java
    Replies: 9
    Last Post: 02-17-2010, 01:02 PM
  2. print random numbers without repetition
    By princess.blue in forum New To Java
    Replies: 3
    Last Post: 02-04-2010, 09:37 AM
  3. how to multiply numbers in rows and print it next to it
    By racewithferrari in forum New To Java
    Replies: 1
    Last Post: 01-16-2010, 06:24 PM
  4. Prime Number - System print all the prime numbers ...
    By pinkdreammsss in forum New To Java
    Replies: 20
    Last Post: 04-26-2009, 01:50 AM
  5. printing two smallest numbers from a series of numbers
    By trofyscarz in forum New To Java
    Replies: 2
    Last Post: 10-14-2008, 11:46 PM

Posting Permissions

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