# Thread: using backtracking to print all possible orders of numbers

1. Member
Join Date
Sep 2010
Posts
4
Rep Power
0

## 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. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
14
Also posted at coding forums.

3. Member
Join Date
Sep 2010
Posts
4
Rep Power
0
well, i didn't know it is the same forum. still, any ideas?

4. Originally Posted by yotamoo
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

5. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
14
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).

#### Posting Permissions

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