CODEWITHSUNDEEP
javadynamicdynamic-programmingknapsack-problem
Simon Kiely
Simon Kiely

Reputation: 6050

Code sometimes returns Integer.MAX_VALUE.Cannot figure out why

I am trying to write code to return the lowest number of coins needed to make up a given number. The inputs to my method are an array of valid coins, and the number I try to make.

    public static int change(int[] d, int p) {
        int[] tempArray = new int[p + 1]; // tempArray to store set
                                            // of coins forming
                                            // answer
        for (int i = 1; i <= p; i++) { // cycling up to the wanted value
            int min = Integer.MAX_VALUE; // assigning current minimum number of
                                            // coins
            for (int value : d) {// cycling through possible values
                if (value <= i) {
                    if (1 + tempArray[i - value] < min) { // if current value is
                                                            // less than min
                        min = 1 + tempArray[i - value];// assign it
                    }
                }
            }
            tempArray[i] = min; // assign min value to array of coins
        }
        return tempArray[p];
    }

This works for most cases, however, when I fill in the following :

int[] test = {2,3,4};
System.out.println("answer = " + change(test, 6));

The answer should be 2, right? But it prints out :

-2147483647

What have I missed?

Upvotes: 0

Views: 347

Answers (1)

srkavin
srkavin

Reputation: 1180

Because, during the first iteration tempArray[i] = min; tempArray[i] is assigned to MAX, and during subsequent iteration[s], min = 1 + tempArray[i - value]; would try to increment MAX by one, which basically shifts the bits and forms a negative counterpart.

Upvotes: 2

Related Questions