Question #2. A country has coins with denominations d1, d2, ..., dk Design a dyn
ID: 3567076 • Letter: Q
Question
Question #2.
A country has coins with denominations d1, d2, ..., dk Design a dynamic programming solution to make change for n cents, using the smallest number of coins. Using your algorithm, find the smallest number of coins to change 15 cents with denominations 1, 2, 7, 8, 10 cents. Show the solution of the sub problems involved using a table. When you have a set of n people, how many ways are there to choose a committee of k members, that is, a k-element subset? It can be represented by the notation C(n, k). The order in which you choose the people who end up in the committee doesn't matter: that is, first choosing Alice, then Bob and then Carol is the same as first choosing Carol, then Bob and then Alice. Define the problem recursively, and use dynamic programming to solve the problem. Compute the values of C(6, 3) storing the values of the sub problems (say C(1, 1), C(2, 1), etc.) in a table. (Hint: first think how you can define C(n, k) recursively.)Explanation / Answer
Q1) To Compute C(n,k) we can define following recursive relation
C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1
so instead of solving subproblems (C(n-1, k-1) and C(n-1, k)) we will Dynamic Programming concepts That is
recomputations of same subproblems can be avoided by constructing a temporary array C[][] in bottom up manner.
// A space optimized Dynamic Programming Solution
int binomialCoeff(int n, int k)
{
C[0] = 1;
for(i = 1; i <= n; i++)
{
for(j = min(i,k); j > 0; j--)
C[j] = C[j] + C[j-1];
}
return C[k];
}
Q2)
we can do it recursively S[] is the array of denomination cents and n is the gven cents
int count( int S[],int n )
{
if (n == 0)
return 0;
if (n < 0)
return 1000000;
else{
min = 100000;
for i in range(len(s)):
if (1 + count(s,n-s[i]) < min):
min = 1 + count(s,n-s[i]);
}
return min;
}
so dynamically we have to store the value of count(s,n-s[i]) in an array. this can be done as take an array of size[n] and start filling it bottom up to use the value of sub roblem;