• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursion  RSS feed

 
Todd Rushing
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am trying to make a program that will take a given weight for a backpack as user input, and will go through a random array of five numbers to find the combination that will add up to the user's given weight. I think i have a general idea of how this would work, but i would like to use recursion for this problem. I am kinda lost now, so any and all help is appreciated.
 
James Carman
Ranch Hand
Posts: 580
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What do you have so far?
 
Todd Rushing
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, i only have ideas of the combination i can use to solve for which weights will add up to the defined weight, other than that, there is no code.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Todd Rushing:
I am trying to make a program that will take a given weight for a backpack as user input, and will go through a random array of five numbers to find the combination that will add up to the user's given weight. I think i have a general idea of how this would work, but i would like to use recursion for this problem. I am kinda lost now, so any and all help is appreciated.


Recursion is a technique just like any other. You don't use it because you "like to use" it for a problem. Either it fits with your "general idea" or it doesn't.

Henry
 
Todd Rushing
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
im pretty sure i can figure out how its done using a loop, but i was wondering if it is possible with recursion, and how that is done
 
Todd Rushing
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's what ive got so far, but obviously i am not to good with grasping the concept of recursion at al, i think i need to completely start over

import javax.swing.JOptionPane;
import java.util.Random;
public class backpack{


int itemCount;
int maxWeight;

public static void main(String[] args){
int[] packItems = new int[5];
double x;
int n;

Random myRandom = new Random();

// make the array!
for (int i = 0; i < 5; i++) {
packItems[i] = 0;
}

for (long i=0; i < 20; i++) {
// generate a new random number between 0 and 9
x = myRandom.nextDouble() * 10.0;
n = (int) x;

packItems[n]++;
}

public int testWeight(){
if((packItems[itemCount]+packItems[itemCount-1]+packItems[itemCount+1]) == 20){
System.out.println("The Combination is:" + packItems[itemCount]);
}
else
{
itemCount ++;
return testWeight();
}
}
}
}
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It looks like you are just taking a looping algorithm, and forcing it to be recursive. And ...

I don't think the looping algorithm works. What if the solution requires items that are not next to each other to be packed.

Henry
 
Ryan McGuire
Ranch Hand
Posts: 1143
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think I understand what you're trying to do.

Try making method (rather than trying to make main() recursive) that takes the current stat of the backpack and the number of items left to do. This method would pack one item and then call itself with the number of items yet to go decremented by one. Use the return code to signify whether the packing has been sucessfully completed. And use the return at each level to determine whether or not to try another random number.

It obviously still needs some details worked out, but there are the basics.

Ryan
 
M Beck
Ranch Hand
Posts: 323
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
in theory, recursion is more general than iteration — that is, anything you can do with an iterative loop, you can also do with a recursive function. (provided you can figure out how to write it, of course, and provided it doesn't recurse too deeply for your language's stack.)

then again, in theory "call/cc" is the most general control structure around, but personally i'm just as happy having if/then/else and switch to use instead...

[edit: corrected thinko.]
[ May 14, 2005: Message edited by: M Beck ]
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!