Data Structures and Algorithm Analysis2d arrays in Java. This program will return the smallest number of coins. There are 3 different type of coins. We have 10cent coin, 6 cent coin, and 1 cent coins. For example if i wanted to give 12 cents, using the 3 coins, i will give 2 coins of 6cents coin and 6cents coin which make up 12 cents. 10 cents coin 6 cents coin 1 cent coin if i wanted to give 9 cents, the least number i can give is 4 coins. i will give 6cent coin + 1cent coin+1cent coin+1cent coin total 9 cents with 4 coins. For this assignment, you will have to use 2d array to setup the coins. row 1 has 3 coins that return the least # of coin row 2 has 2 coins(6cent coin and 1 cent coin) row 3 has only 1 cent coin please also provide algorithm or flow chart If you have any further question please contact me via email.Coin Changing Problem:
Develop a program that makes change for an amount A using the fewest number of coins, where the available denominations were
denom[1] > denom[2] > ... > denom[n] = 1
You cannot use the following greedy algorithm, which may or may not lead to an optimal solution, i.e. the fewest number of coins, depended on which denominations of coins were available.
Greedy_coin_change(denom, A) { i = 1;
while (A > 0) {
c = A/denom[i];
println("use " + c + " coins of denomination " + denom[i]); A = A - c * denom[i];
i = i + 1;
}
}
Instead, you are required to develop a dynamic-programming solution for the coin-changing problem no matter which denominations are available.
According to dynamic programming, you can break the given problem into subproblems by considering the i, j-problem of computing the minimum number of coins for an amount j, 0 <= j <= A, where the available denominations are
denom[i] > denom[i+1] > ... > denom[n] = 1, 1 <= i <= n
The original problem is i = 1 and j = A. We let C[i][j] denote the solution to the problem; that is, C[i][j] is the minimum number of coins to make change for the amount j, using coins i through n. The following table shows an example: the array C for the denominations denom[1] = 10, denom[2] = 6, and denom[3] = 1 and amount up to 12. The index i specifies that coins i through 3 are available, and j is the amount. When i = 3, only of the coin of denomination 1 is available. Thus, in the last row, it takes j coins to make change for the amount j. When i = 2, the coins 6 and 1 are available. For example, the minimum number of coins to make change for the amount 8 is three---one coin of denomination 6 and tow coins of denomination 1. When i = 1, all of the coins are available. For example, the answer for the amount 11 is two---one coin of denomination 10 and one coin of denomination 1.
i, j 0 1 2 3 4 5 6 7 8 9 10 11 12
|
1
|
0
|
1
|
2
|
3
|
4
|
5
|
1
|
2
|
3
|
4
|
1
|
2
|
2
|
|
2
|
0
|
1
|
2
|
3
|
4
|
5
|
1
|
2
|
3
|
4
|
5
|
6
|
2
|
|
3
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
To solve the i,j-problem, i < n, we must decide whether to use a coin of denomination denom[i]. if we do not use denom[i], we, in order to achieve the amount j, must solve (i+1), j-problem that is a subproblem (a smaller problem in the sense that fewer coins are available). In this case C[i][j] = C[i+1][j]. On the other hand, if we use denom[i], we must complete the solution by making change for the amount j-denom[i] using coins of denom[i], denom[i+1], ..., denom[n] = 1; that is a i, (j-denom[i])-problem.
Thus depended upon whether coin i should be used, the solution to the i,j-problem is?
Deliverables
1. Well written algorithm or flow chart of your program
2. The source code and testing data including inputs and outputs
3. The class or executable file