Ask Question
15 June, 01:06

Given coins of denominations (value) 1 = v1 < v2< ... < vn, we wish to make change for an amount A using as few coins as possible. Assume that vi's and A are integers. Since v1 = 1 there will always be a solution. Solve the coin change using integer programming. For each the following denomination sets and amounts formulate the problem as an integer program with an objective function and constraints, determine the optimal solution.

What is the minimum number of coins used in each case and how many of each coin is used? Include a copy of your code.

a) V = [1, 5, 10, 25] and A = 202.

b) V = [1, 3, 7, 12, 27] and A = 293

+1
Answers (1)
  1. 15 June, 02:20
    0
    Answer given below

    Explanation:

    a) 10 coins (25*8 + 1*2)

    b) 14 coins (27*10 + 12*1 + 7*1 + 3*1 + 1*1)

    Source Code in C++:

    #include

    using namespace std;

    //main function

    int main ()

    {

    int n, n1;

    cout << "Enter the amount : "; / /taking amount as input

    cin >> n;

    if (n<=0)

    {

    cout << "Fatal Error : Input Failure." << endl;

    return 1;

    }

    cout << "Enter the number of denominations : "; / /taking number of denominations as input

    cin >> n1;

    if (n1<=0)

    {

    cout << "Fatal Error : Input Failure." << endl;

    return 1;

    }

    int a[n1], c[n1], sum=0; / /array to keep count of each amount, and sum to store total coins

    cout << "Enter the denominations in descending order : ";

    for (int i=0; i
    {

    cin >> a[i];

    }

    for (int i=0; i
    {

    c[i]=n/a[i];

    sum=sum+c[i];

    n=n%a[i];

    }

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

    {

    cout << a[i] << " : " << c[i] << endl;

    }

    return 0;

    }
Know the Answer?
Not Sure About the Answer?
Find an answer to your question ✅ “Given coins of denominations (value) 1 = v1 < v2< ... < vn, we wish to make change for an amount A using as few coins as possible. Assume ...” in 📘 Computers and Technology if you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers