1. Member
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;
}
}

2. Java 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, size-1, 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.length-1)
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;
}
}

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•