# using backtracking to print all possible orders of numbers

• 12-07-2010, 12:26 AM
yotamoo
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
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:
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!
• 12-07-2010, 01:21 AM
pbrockway2
Also posted at coding forums.
• 12-07-2010, 02:44 AM
Eranga
Oh, I hate cross-posting.
• 12-07-2010, 11:53 AM
yotamoo
well, i didn't know it is the same forum. still, any ideas?
• 12-07-2010, 12:32 PM
JosAH
Quote:

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
• 12-07-2010, 09:23 PM
pbrockway2
Quote:

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).
• 12-08-2010, 01:39 AM
Eranga
It's an interesting article pbrockway2.