• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Recursion

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Ranch Hand
Posts: 580
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What do you have so far?
 
Todd Rushing
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Ranch Hand
Posts: 323
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ]
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic