Saturday, December 21, 2013

Find the min number of coin to get sum S

public class FindMinCoin {

    public void findMinCoin() {
        int valueCoins[] = new int[]{1, 3, 5};
        int sum = 11;
        int min[] = new int[sum + 1];
       
        // assign sum to infinity
        for(int i=1; i<min.length; i++)
            min[i] = 999999;
       
        // initialize min sum = 0
        min[0] = 0;
       
        for(int i=1; i<= sum; i++)
            for(int j=0; j<valueCoins.length; j++){
                if(valueCoins[j] == i){
                    min[i] = 1;
                }else if((valueCoins[j] < i) && (((min[i-valueCoins[j]]) + 1) < min[i])){
                    min[i] = (min[i-valueCoins[j]]) + 1;
                }
            }
       
        for(int k=1; k<min.length; k++){
            System.out.println(k + " " + min[k] + " ");
        }      
    }

    public void printArr(int coins[][], int min[]){
        System.out.println("Min:-----------");
        for(int i=0; i<min.length; i++)
            System.out.println("min[" + i + "] = " + min[i]);
       
        System.out.println("Coins:--------");
        for(int i=0; i<coins.length; i++)
            System.out.println("conins[" + i + "][0] = " + coins[i][0] + "\tcoins[" + i + "][1]=" + coins[i][1]);
    }
   
    public static void main(String args[]) {
        FindMinCoin fmc = new FindMinCoin();
        fmc.findMinCoin();
    }
}

No comments:

Post a Comment