Reference no: EM131110624
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
|
Define the ethical duties of a trial lawyer
: Define the ethical duties of a trial lawyer under the legal profession
|
|
The company sustained a net loss for the year
: Uncollectible accounts receivable in the amount of $22,000 were written off against the Allowance for Doubtful Accounts.
|
|
Read in the interest rate
: In C++ Using a while loop, code and run a program that will calculate how long it will take $10,000.00 to become $1,000,000 with 0.08 interest rate.
|
|
How high above the center of a circle of radius 10.0 in
: How high above the center of a circle of radius 10.0 in. should a light be placed so that illuminance at the circumference will be a maximum? See Fig. 27.51.
|
|
Data structures and algorithm analysis2d arrays in java
: 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 t..
|
|
Organizational behaviour week discussion
: Have you ever witnessed escalation of commitment in your organization--or seen it take place with governments? Why do you think that escalation of commitment continued instead of stopping support of the original decision?
|
|
Compute the surface area of t
: Let T ⊂ R3 denote the doughnut-shaped surface obtained by revolving the circle (y - 2)2 + z2 = 1 around the z-axis. Give T the orientation determined by the outward unit normal. Compute the surface area of T
|
|
Compute net cash flow from operating activities
: 1. The net income for Letterman Company for 2010 was $320,000. During 2010, depreciation on plant assets was $124,000, amortization of patent was $40,000, and the company incurred a loss on sale of plant assets of $21,000. Compute net cash flow from ..
|
|
Write a program in c++ to accept a string
: Write a program in C++ to accept a String and print the total no of vowels in it. Also print the string in upper and lower case
|