Results 1 to 7 of 7
 12072010, 12:26 AM #1Member
 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'. 1stolen, 0left.
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<=index1; 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); } }
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
how can i make it right? thank you!
 12072010, 01:21 AM #2Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,708
 Rep Power
 13
Also posted at coding forums.
 12072010, 02:44 AM #3
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 20
 12072010, 11:53 AM #4Member
 Join Date
 Sep 2010
 Posts
 4
 Rep Power
 0
well, i didn't know it is the same forum. still, any ideas?
 12072010, 12:32 PM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,000
 Blog Entries
 7
 Rep Power
 23
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 NSPI or NSP, i.e. you either take item I or you don't. If you take item I your knapsack can still carry Ww where W is the weight of the empty knapsack and the total value is V(NSPI)+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,
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 12072010, 09:23 PM #6Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,708
 Rep Power
 13
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).
 12082010, 01:39 AM #7
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 20
It's an interesting article pbrockway2.
Similar Threads

need help with backtracking
By Dumisan in forum Advanced JavaReplies: 9Last Post: 02172010, 02:02 PM 
print random numbers without repetition
By princess.blue in forum New To JavaReplies: 3Last Post: 02042010, 10:37 AM 
how to multiply numbers in rows and print it next to it
By racewithferrari in forum New To JavaReplies: 1Last Post: 01162010, 07:24 PM 
Prime Number  System print all the prime numbers ...
By pinkdreammsss in forum New To JavaReplies: 20Last Post: 04262009, 01:50 AM 
printing two smallest numbers from a series of numbers
By trofyscarz in forum New To JavaReplies: 2Last Post: 10142008, 11:46 PM
Bookmarks