1 answer

Problem: Implement (in C) the dynamic program algorithm for the coin-change algorithm, discussed in class. Assume...

Question:

Problem: Implement (in C) the dynamic program algorithm for the coin-change algorithm, discussed in class. Assume that the coins with which you make change are quarters, dimes, nickels and pennies. Thus you are going to set n = 4 in your program. The amount k for which you have to make change will be provided by the user and your program will return the minimum number of coins needed and also the break-up of the change in terms of the different denominations used. Thus if the input is 31, the output for the minimum number of coins needed would be 3 and the break-up 25 + 5 + 1. (10 points)


Answers

CODE

#include<stdio.h>

#include <limits.h>

// m is size of coins array (number of different coins)

int minCoins(int coins[], int m, int V)

{

// base case

if (V == 0) return 0;

// Initialize result

int res = INT_MAX;

// Try every coin that has smaller value than V

for (int i=0; i<m; i++)

{

if (coins[i] <= V)

{

int sub_res = minCoins(coins, m, V-coins[i]);

// Check for INT_MAX to avoid overflow and see if

// result can minimized

if (sub_res != INT_MAX && sub_res + 1 < res)

res = sub_res + 1;

}

}

return res;

}

// Driver program to test above function

int main()

{

  int i, j;

  int arr[] = {1, 5, 10, 25};

  int n = 4;

int k;

printf("Enter the amount: ");

scanf("%d", &k);

  printf("%d ", minCoins(arr, n, k));

  getchar();

  return 0;

}

.

Similar Solved Questions

1 answer
(a) If your life plan is to buy one lottery ticket every day for 5 days...
(a) If your life plan is to buy one lottery ticket every day for 5 days a week, 50 weeks a year for the next 50 years, where on any lottery ticket you have a one in 500,000,000 chance of winning the jackpot, what is the probability you will win the jackpot at least once in your lifetime? Hint: Let W...
1 answer
The bulk modulus is used to measure the: Strain hardening of a material Stiffness of a...
The bulk modulus is used to measure the: Strain hardening of a material Stiffness of a volume of a material Volumetric strain of a material Resistance to lateral straining of a volume of material Question 50 Dilatation is a measure of. O Volumetric strain O Swelling O Stress concentrations Strain co...
1 answer
Answer both parts please 3. Implement a Mealy FSM to detect the "1100110” sequence with overlap....
Answer both parts please 3. Implement a Mealy FSM to detect the "1100110” sequence with overlap. The output Y should be a 'l' only when the sequence has been detected and 'O' otherwise. Obtain the state transition diagram, state transition table, state assignment table, out...
1 answer
Pament i Cognitive Inpaiment A X Mps://onedrive.lv.com/Editamparesid-22E2A8974EDERSE:1203 Cognitive Impairment Assignment (1) 1 . Saved to OneDrive...
pament i Cognitive Inpaiment A X Mps://onedrive.lv.com/Editamparesid-22E2A8974EDERSE:1203 Cognitive Impairment Assignment (1) 1 . Saved to OneDrive Insert Layout References Review View Help Open in Desktop App Comic Sans MS 12 AA BI U OVA... VE Search ... Av 7. Mr. Black, age 89, has multi-infarct d...
1 answer
Explain why you shouldn’t use a temporal artery thermometer to measure core body temperature over the...
Explain why you shouldn’t use a temporal artery thermometer to measure core body temperature over the radial artery....
1 answer
Adamson Corporation is considering four average-risk projects with the following costs and rates of return: Project C...
Adamson Corporation is considering four average-risk projects with the following costs and rates of return: Project Cost Expected Rate of Return 1 $2,000 16.00% 2 3,000 15.00 3 5,000 13.75 4 2,000 12.50 The company estimates that it can issue debt at a rate of rd = 11%, and its tax rat...
1 answer
Predict the larger ion in each of the following pairs. (a)   Sr2+ or Rb+   _________strontium ionrubidium ion...
Predict the larger ion in each of the following pairs. (a)   Sr2+ or Rb+   _________strontium ionrubidium ion (b)   Cr3+ or Cr2+   _________chromium(III) ionchromium(II) ion (c)   O- or O2-   _________oxygen -1 iono...
1 answer
1 Name a main group element in the fourth period (row) of the periodic table with...
1 Name a main group element in the fourth period (row) of the periodic table with four valence electrons. Express your answer as a chemical symbol (ex: He)....
1 answer
Problem-Solving Strategies: Guide to Using the Gas Laws 21 of 29 Part A - Organize the...
Problem-Solving Strategies: Guide to Using the Gas Laws 21 of 29 Part A - Organize the data Since volume and pressure are inversely related, we can make some assumptions about initial and final states using the data provided. We can also identify initial and final states by finding trigger words in ...
1 answer
How do you solve #-13=-h-7#?
How do you solve #-13=-h-7#?...
1 answer
A flash lamp is placed at the center of a solid sphere of dense flint glass...
A flash lamp is placed at the center of a solid sphere of dense flint glass of radius 1.00 m. A second, identical flash lamp is placed at the center of a solid sphere of quartz also of radius 1.00 m. At the same instant both lamps are turned on, each producing a flash of white light (that is, light ...
1 answer
How does electromagnetic spectrum work?
How does electromagnetic spectrum work?...
1 answer
13. Evaluate the F across S. For closed surfaces, use the positive (outward) orlentacion. S is the cube with vertices (,1) Sbrit Anser Save Progress Practice Another Vension My Nodes Aak Your Eva...
13. Evaluate the F across S. For closed surfaces, use the positive (outward) orlentacion. S is the cube with vertices (,1) Sbrit Anser Save Progress Practice Another Vension My Nodes Aak Your Evaluate the surface integral F S for the given vector field F and the oriented surface S. In other words, f...
1 answer
How do you solve #9j + 16= 3j + 21#?
How do you solve #9j + 16= 3j + 21#?...
1 answer
Ross has a checking account with $50,000 and savings account with $250,000 at SunTrust Bank. He...
Ross has a checking account with $50,000 and savings account with $250,000 at SunTrust Bank. He has an IRA account at SunTrust Bank with $500,000 in it. He and his wife have a certificate of deposit at SunTrust Bank worth $100,000. How much would FDIC insurance pay if SunTrust Bank failed?...
1 answer
Assume that the items in the population to be sampled follow an F distribution, not a...
Assume that the items in the population to be sampled follow an F distribution, not a normal distribution. Is it appropriate to do statistical sampling? Why or why not?...