Help with recursion

[scts102]

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.

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;
            }
    }

Thanks in advance!

[hardwired]

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;
    }
}