DynamicCoinChange

src_java_CoinChange_Dynamic.java

package CoinChange;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeSet;

/**
 * Created by Sanitarium on 4/15/2016.
 */

public class Dynamic {

    public int D_Change(TreeSet<Integer> coins, int Money)
    {
        ArrayList C = new ArrayList(Money+1);
        ArrayList S = new ArrayList(Money+1);
        C.add(0);

        for(int j =0; j <= Money; j++ )
        {
          C.add(Integer.MAX_VALUE);
            Iterator iterator = coins.iterator();
            int x =0;
            while(iterator.hasNext())
          {
              int  temp= (int)iterator.next();
              if (j >= temp && (1 + (int)C.get(j - temp)) < (int)C.get(j))
              {
                  C.set(j,(1+(int)C.get(j - temp)));
                  S.add(temp);

              }
              x++;
          }

        }


        return (int)C.get(Money);

    }
}

src_java_CoinChange_Greedy.java

package CoinChange;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeSet;

/**
 * Created by Sanitarium on 4/15/2016.
 */


// COINS 1, 5, 10, 25
public class Greedy {

 public ArrayList GreedyChange(TreeSet<Integer> coins, int Money)
 {
     int Check_Change = Money;
     ArrayList Change = new ArrayList();


     while (Check_Change != 0)
     {
        Iterator it = coins.descendingIterator();

         while (it.hasNext())
         {
            int temp = (int)it.next();
             if (Check_Change - temp > -1 )//greater than or equal to 0
             {
                 Change.add(temp);
                 Check_Change  =  Check_Change - temp;
                 break;
             }
         }
     }

     return  Change;

 }
}

src_java_CoinChange_WorkWork.java

package CoinChange;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;


/**
 * Created by Sanitarium on 4/15/2016.
 */
public class WorkWork {

    public static Greedy greedy = new Greedy();
    public static Dynamic dynamic = new Dynamic();

    public static void main(String args[])
    {
        // COINS 1, 5, 10, 25
        Set<Integer> set = new HashSet<Integer>();
        set.add(1);
        set.add(5);
        set.add(10);
        set.add(25);
        TreeSet<Integer> Denominations = new TreeSet<Integer>(set);
        int money = 102;
//        ArrayList Received = greedy.GreedyChange(Denominations, money);
//
//        System.out.println("Coins List: " + Received);

        int coins = dynamic.D_Change(Denominations,money);


        System.out.println(coins);

    }
}