Beginning Dynamic Programming - Greedy coin change help

Question

I am currently working through a book on algorithm design and came across a question whereby you must implement a greedy algorithm with dynamic programming to solve the coin change problem.

I was trying to implement this and I just can't figure out out or make sense of the algorithm given in my book. The algorithm is as follows(with my (lack of) understanding in comments) :

Change(p) {
  C[0] = 0
    for(i=1 to p) //cycling from 1 to the value of change we want, p
      min = infinity
        for(j=1 to k( //cyle from 1 to...?
          if dj <=i then
            if(1+C[i-dj] < min) then
               min = 1+C[i-dj]
            endif
          endif
        endfor
     C[i] = min
    endfor
  return C[p]
}

And my attempt at interpreting what's going on :

/**
     * 
     * @param d
     *            currency divisions
     * @param p
     *            target
     * @return number of coins
     */
    public static int change(int[] d, int p) {
        int[] tempArray = new int[Integer.MAX_VALUE]; // 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 coints
            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[1 - value];//assign it
                    }
                }
            }
            tempArray[i] = min; //assign min value to array of coins
        }
        System.out.println("help"); // :(
        return tempArray[p];
    }

Can someone please explain to me what I am missing, how to fix this, and how this algorithm is supposed to work? Dynamic Programming seems like such a useful tool, but I cannot get my head around it. I keep thinking recursively.

Answer 1

see this wikipedia link

an excerpt:

Greedy choice property We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution.

Your code iterates through the int p gets the optimum choice and puts it into the array tempArray then uses this value to check the optimum choice in the next iteration.

Answer 2

the essence of dynamic programming is to break down the problems into sub-problems and then start building the solution upwards. The idea is if you solve "n" sub-problems you can combine them and the combination would be the solution to the whole problem. Recursion is an example of dynamic programming except that it suffers from potential stack overflow issues. The other technique is called memoization which caches results for faster lookup times rather than recomputing already computed problems. This saves a lot processing and speeds the program up. As for the greedy coin change problem, the essence is to look for the largest denomination and use it until it can't be used anymore (i.e. divide the total amount repeatedly by largest denomination and keep track of the remainder) then move on to the next largest and repeat the same process until you are left with the lowest amount that can be represented by the smallest denomination. You can store the min value in an array all along and keep updating it if a new minimum is found (i.e. memoization). I hope people can correct me if i m wrong somewhere.

EDIT: however note that not all problems can be solved by dynamic programming and dynamic programming has got nothing to do with any programming language, instead its just a name of the technique that is employed to solve optimisation problems.

Answer 3

This seems to be HW problem so I will be giving few pointers.The first thing to do, to solve a problem by DP is "Think Top Dwon and solve bottom up".

"Think Top Down " - This is the part where you formulate your the recursive relation

For Eg: T(n) = 0 if n<1 or T(n-1) otherwise;

The recursive relation relies on the previously computed sub problems.

"Solve Bottom Up" - This is the part where your code will solve the problem bottom up based on the above found recursive relation.

Usually Coding is simple and the tougher part is coming up with a good recursive relation( Though there will be no recursion).

Answer 4

A little late to the party, but your function already works.

public static int change(int[] d, int p) {
    // tempArray to store set of coins forming answer
    int[] tempArray = new int[Integer.MAX_VALUE];

    tempArray[0] = 0; // INITIAL STEP MISSING

    for (int i = 1; i <= p; ++i) { // cycling up to the wanted value
        // assigning current minimum number of coins
        int min = Integer.MAX_VALUE;

        // cycling through possible values
        for (int value : d) {

            if (value <= i) { // FIX missing = in <=

                // if current value is less than min
                if (1 + tempArray[i - value] < min) {

                    // FIX, it's [i-value] not [1-value]
                    min = 1 + tempArray[i - value];
                }
            }
        }
        tempArray[i] = min; // assign min value to array of coins
    }
    return tempArray[p];
}

And using it.

public static void main(String[] args) {
    int[] coins = new int[] { 25, 12, 10, 5, 1 };

    int coinCount = change(coins, 15);
    System.out.println("min change: " + coinCount);
}