Results 1 to 2 of 2
Thread: Help with recursion
 11192007, 02:01 AM #1Member
 Join Date
 Nov 2007
 Posts
 1
 Rep Power
 0
Help with recursion
Hello. I need some help with recursion. Given an array of integers, I have to return the sum of integers that is closest to goalWeight without going over. My code works for some test sets, but not all. I was wondering if someone could take a look at my code and tell me what I am doing wrong...
Note: vars with and without represent calls made, including and excluding A[first], respectively. first and last represent the first and last elements in the array.
Java Code:public int maxPack(int[] A, int first, int last, int goalWeight) { int maxWeight = 0; int with=0; int without = 0; if(goalWeight <=0) return 0; if(first == last){ if(A[first] <= goalWeight) maxWeight += A[first]; return maxWeight; } else{ if (A[first] <= goalWeight) { with += A[first]; with += maxPack(A, first + 1, last, (goalWeight  A[first])); } without += maxPack(A, first + 1, last, goalWeight); if(with < goalWeight  without < goalWeight){ if(without < goalWeight){ if(with > without) { maxWeight += with; return maxWeight; } else { maxWeight += without; return maxWeight; } } else{ assert(with < goalWeight); maxWeight += with; return maxWeight; } } return 0; } }
 11192007, 11:07 PM #2Java Code:
import java.util.*; public class Recurse { static Random seed = new Random(); public static void main(String[] args) { int limit = 16; int size = 10; int maxVal = 25; for(int j = 0; j < 5; j++) { int[] n = getArray(limit, size); System.out.printf("n = %s maxVal = %d%n", Arrays.toString(n), maxVal); System.out.printf(" getMax() = %d%n", getMax(n, maxVal, 0, 0)); System.out.printf(" getSum() = %d%n", getSum(n, maxVal)); System.out.printf("maxPack() = %d%n", maxPack(n, 0, size1, maxVal)); System.out.println(""); } } private static int getMax(int[] array, int maxValue, int index, int value) { if(value + array[index] <= maxValue) value += array[index]; else return value; if(index == array.length1) return value; return getMax(array, maxValue, index+1, value); } private static int getSum(int[] array, int goalWeight) { int weight = 0; for(int j = 0; j < array.length; j++) { if(weight + array[j] > goalWeight) break; weight += array[j]; } return weight; } private static int maxPack(int[] A, int first, int last, int goalWeight) { int maxWeight = 0; int with = 0; int without = 0; if(goalWeight <= 0) return 0; if(first == last){ if(A[first] <= goalWeight) maxWeight += A[first]; return maxWeight; } else{ if (A[first] <= goalWeight) { with += A[first]; with += maxPack(A, first + 1, last, (goalWeight  A[first])); } without += maxPack(A, first + 1, last, goalWeight); if(with < goalWeight  without < goalWeight){ if(without < goalWeight){ if(with > without) { maxWeight += with; return maxWeight; } else { maxWeight += without; return maxWeight; } } else{ assert(with < goalWeight); maxWeight += with; return maxWeight; } } return 0; } } private static int[] getArray(int limit, int size) { int[] n = new int[size]; Arrays.fill(n, limit+1); int count = 0; while(count < size) { int candidate = seed.nextInt(limit+1); if(!contains(n, candidate)) n[count++] = candidate; } return n; } private static boolean contains(int[] array, int target) { for(int j = 0; j < array.length; j++) { if(array[j] == target) return true; } return false; } }
Similar Threads

Help With Recursion
By andrew777 in forum New To JavaReplies: 1Last Post: 03292008, 01:51 PM 
recursion
By kdeighan in forum New To JavaReplies: 3Last Post: 01252008, 10:48 PM 
Recursion
By bozovilla in forum Advanced JavaReplies: 3Last Post: 01072008, 05:53 PM 
recursion
By ravian in forum New To JavaReplies: 2Last Post: 12032007, 06:15 PM 
Recursion in java
By lenny in forum Advanced JavaReplies: 1Last Post: 08072007, 06:23 AM
Bookmarks