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 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

Answer 1

Answer:

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 <iostream>

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<n1;i++)

{

cin >> a[i];

}

for(int i=0;i<n1;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;

}