Using a Stack instead of recursive calls

Don't understand why this implementation of the stack isn't wo

Page 1 of 1

6 Replies - 3353 Views - Last Post: 23 May 2010 - 11:26 AM Rate Topic: -----

#1 javaNovice83  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 21-May 10

Using a Stack instead of recursive calls

Posted 21 May 2010 - 05:01 AM

Hi there,

I have done the recursive method and do not know exactly why this implementation of the stack isn't working. Please help! I just don't get how to use the stack for the loop.

The Recursive method:
private void solveRecursive(int i) {
		// do not descend into this object's child nodes, track back
		if(i > objects.length || rs.getAvailableCapacity() < 0){
			return;
		}
		// if not rejected current rucksack is best rucksack
		if(rs.getTotalValue() > maxValue){
			maxValue = rs.getTotalValue();
			bestRuck.copyFrom(rs);
		} 
		// we add the object only if its weight is <= available capacity
		if(i < objects.length && objects[i].getWeight() <= rs.getAvailableCapacity()){
			rs.putObject(objects[i]);
			solveRecursive(i+1);
			// we remove it so that we can recurse the function without it
			rs.removeObject(objects[i]);
		}
		// recurse the function without object i
		solveRecursive(i+1);
	}


The incorrect iterative using stack method:
public void solveIterative() {
		
		// A stack to use with the algorithm
		Deque<Integer> stack = new LinkedList<Integer>();
		// The current position in the array of objects
		int i = 0;
		stack.push(i);
						
		while(!stack.isEmpty()){
			int j = stack.pop();
			
			if(j > objects.length || rs.getAvailableCapacity() < 0){
				return;
			}
			if(rs.getTotalValue() > maxValue){
				maxValue = rs.getTotalValue();
				bestRuck.copyFrom(rs);
			}
			// to add the object
			if(j < objects.length && objects[j].getWeight() <= rs.getAvailableCapacity()){
				rs.putObject(objects[j]);
				stack.push(j+1);
				
			}
			else{
				if(j < objects.length){
					rs.removeObject(objects[j-1]);
					j--;
				}
				
			}
		}
	}



Any help would be Greatly appreciated!!!

Thanks!!!

Is This A Good Question/Topic? 0
  • +

Replies To: Using a Stack instead of recursive calls

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10461
  • View blog
  • Posts: 38,753
  • Joined: 27-December 08

Re: Using a Stack instead of recursive calls

Posted 21 May 2010 - 05:11 AM

What exactly is your problem or error? What isn't working? What is the result you are getting instead?Also, what exactly are you trying to accomplish? Any additional information would be helpful. :)
Was This Post Helpful? 0
  • +
  • -

#3 javaNovice83  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 21-May 10

Re: Using a Stack instead of recursive calls

Posted 21 May 2010 - 05:21 AM

Oops so sorry....

The question is to find a solution to the Knapsack problem where we are given n different objects, each with a weight and value; and a Knapsack of a fixed capacity. We are to find the most optimal combination of objects with a total weight less than the Knapsack's capacity and the maximum possible total value.

I represent the solution to this problem as a tree, where the nodes represent the objects. Traversing to the right child node means adding the object to the Knapsack and to the left is not to add the object.

The stack implementation doesn't work as it adds only the nodes from the root to the leaf on the right but doesn't backtrack to check the combinations of other nodes.

I hope what I'm trying to get across is clear. Thanks for the super fast attention!
Was This Post Helpful? 0
  • +
  • -

#4 SpeedisaVirus  Icon User is offline

  • Baller
  • member icon

Reputation: 114
  • View blog
  • Posts: 855
  • Joined: 06-October 08

Re: Using a Stack instead of recursive calls

Posted 22 May 2010 - 07:31 PM

EDIT: I'm pretty sure I'm really really wrong there...don't listen to me :whistling:

This post has been edited by SpeedisaVirus: 22 May 2010 - 07:43 PM

Was This Post Helpful? 0
  • +
  • -

#5 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8328
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Using a Stack instead of recursive calls

Posted 22 May 2010 - 07:45 PM

The question is quite philosophical
using a Stack or using recursion ?
Recursion is using the standard call frames stack as storage using your own Stack is just doing it yourself instead of letting the OS to do it for you
So in both cases you are using a stack
Was This Post Helpful? 2
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10461
  • View blog
  • Posts: 38,753
  • Joined: 27-December 08

Re: Using a Stack instead of recursive calls

Posted 22 May 2010 - 08:28 PM

pbl makes a very good point here. Java uses the call Stack to manage code execution. When a recursive call is made, it is pushed onto the call stack. When it finishes, it is popped from the Stack. So as pbl said, you can either let the call Stack and OS manage this for you or you can manage it yourself.

Also, I've written a snippet which checks to see if you can exactly fill the knapsack of size n given weights int[] x, which you may find helpful for a starting point. You may also want to think about modeling this after Mergesort. So when you get to the base case, return the more optimal solution. As the recursive calls are popped and you go up a level each time, the more optimal solutions will be returned until you get the most optimal solution.

Link to my snippet: http://www.dreaminco...snippet5011.htm

This post has been edited by macosxnerd101: 22 May 2010 - 08:29 PM

Was This Post Helpful? 1
  • +
  • -

#7 Guest_René*


Reputation:

Re: Using a Stack instead of recursive calls

Posted 23 May 2010 - 11:26 AM

hi,

if you din´t find a solution till monday you can send me a email. I know that you have to upload your solution till Thusday cause i have to upload it too to get the points for gdi2 ;-)

So if you need help send me a email. <removed>

Edited by macosxnerd101: Removed email. Please keep all work in the forums so that all members can benefit.

This post has been edited by macosxnerd101: 23 May 2010 - 11:54 AM

Was This Post Helpful? 0

Page 1 of 1