Showing posts with label sum s. Show all posts
Showing posts with label sum s. Show all posts

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