Results 1 to 2 of 2
  1. #1
    scts102 is offline Member
    Join Date
    Nov 2007
    Posts
    1
    Rep Power
    0

    Default 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;
                }
        }
    Thanks in advance!

  2. #2
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

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

Similar Threads

  1. Help With Recursion
    By andrew777 in forum New To Java
    Replies: 1
    Last Post: 03-29-2008, 12:51 PM
  2. recursion
    By kdeighan in forum New To Java
    Replies: 3
    Last Post: 01-25-2008, 09:48 PM
  3. Recursion
    By bozovilla in forum Advanced Java
    Replies: 3
    Last Post: 01-07-2008, 04:53 PM
  4. recursion
    By ravian in forum New To Java
    Replies: 2
    Last Post: 12-03-2007, 05:15 PM
  5. Recursion in java
    By lenny in forum Advanced Java
    Replies: 1
    Last Post: 08-07-2007, 06:23 AM

Posting Permissions

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