@@ -0,0 +1,1943 @@
+/*Sample demonstration of a greedy algorithm:%0A * Problem is to pick the least number of coins to make a total of N from k coins of denomination set, given coins of denominations D1, D2, D3 ... Dk, where always D1=1%0A * Denomination system considered for this problem is the binary system: D1=1, D2=2, D3=4, D4=8 ....Dk=2%5E(k-1)%0A * Also, we can reuse the same coin multiple times, considering we have infinite supply of every in coin in a denomination D%0A * Example: N=70, k=6.%0A * Thus, denomination set D of length k = %5B1 2 4 8 16 32%5D%0A * Number of coins required = 4%0A * Actual coins required: 32, 32, 4, 2%0A * %0A * Any denomination set can be used like the standard american denomination set (1 cent, 5 cents, 10, 25...), sequential denomination set (1 cent, 2, 3, 4...), etc*/%0A%0Aimport java.io.BufferedReader;%0Aimport java.io.IOException;%0Aimport java.io.InputStreamReader;%0Aimport java.util.ArrayList;%0A%0Apublic class CoinExchange%0A%7B%0A%09public static void main(String args%5B%5D)throws IOException%0A%09%7B%0A%09%09BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));%0A%09%09%0A%09%09System.out.println(%22Enter N: %22);%0A%09%09int n = Integer.parseInt(obj.readLine());%0A%0A%09%09System.out.println(%22Enter k: %22);%0A%09%09int k = Integer.parseInt(obj.readLine());%0A%09%09%0A%09%09int d%5B%5D = new int%5Bk%5D;%0A%09%09int base = 2;%0A%09%09%0A%09%09System.out.print(%22Denomination set D generated: %5B%22);%0A%09%09for(int i=0;i%3Ck;i++)%0A%09%09%7B%0A%09%09%09d%5Bi%5D = (int) Math.pow(base, i);%0A%09%09%09System.out.print(%22D%22 + (i+1) + %22 = %22 + d%5Bi%5D + ((i==k-1) ? %22%5D%22 : %22, %22));%0A%09%09%7D%0A%09%09%0A%09%09ArrayList%3CInteger%3E output = new ArrayList%3CInteger%3E();%0A%09%09int count=0;%0A%09%09%0A%09%09int remainingAmount = n;%0A%09%09%0A%09%09int i=d.length-1;%0A%09%09while(remainingAmount%3E0)%0A%09%09%7B%0A%09%09%09if(d%5Bi%5D%3C=remainingAmount)%0A%09%09%09%7B%0A%09%09%09%09output.add(d%5Bi%5D);%0A%09%09%09%09count++;%0A%09%09%09%09remainingAmount = remainingAmount - d%5Bi%5D;%0A%09%09%09%09i=d.length-1;%0A%09%09%09%7D%0A%09%09%09else%0A%09%09%09%7B%0A%09%09%09%09i-=1;%0A%09%09%09%7D%0A%09%09%7D%0A%09%09%0A%09%09System.out.println(%22%5Cn%5CnNumber of coins required to make %22 + n + %22 : %22 + count);%0A%09%09System.out.println(%22Actual coins required: %22 + output);%0A%09%7D%0A%7D%0A

Create CoinExchange greedy problem