|
Question: You need to spend an exact amount from given types of coins of various denominat.... .....
Microsoft Interview Questions and Answers
(Continued from previous question...)
281. Question:
You need to spend an exact amount from given types of coins of various denominat.... .....
Question:
You need to spend an exact amount from given types of coins of various denominations. There is a cost associated with the type of the coin. You would like to minimize the cost subject to constraint that you can only spend a limited number of coins of each denomination
Input :
coinDenoms = {100,100,300,400,500,600};
coinDenomSize = 6
coinCost = {125,150,425,525,625,725};
coinCostSize = 6
amount = 400
limitPerDenomination = 4
Output :
The function findMinCost() returns an array containing
125,125,125,125
maybe an answer:
I used the algorithm of the 0-1 knapsack problem.
pair<vector<int>,int> findMinCost(const int* coinDenoms,
const int coinDenomSize, const int* coinCost, const int coinCostSize,
const int amount, const int limitPerDenomination) {
vector<int> empty;
pair<vector<int>,int> wrongpair = make_pair(empty,-1);
pair<vector<int>,int> emptypair = make_pair(empty,0);
if (coinDenomSize!=coinCostSize) return wrongpair;
if (amount==0) return emptypair;
if (limitPerDenomination==0) return wrongpair;
if (coinDenomSize==0) return wrongpair;
if (coinDenoms[coinDenomSize-1]>amount)
return findMinCost(coinDenoms,coinDenomSize-1,coinCost,
coinCostSize-1,amount,limitPerDenomination);
pair<vector<int>,int> temp1=findMinCost(coinDenoms,coinDenomSize-1,
coinCost,coinCostSize-1,amount,limitPerDenomination);
pair<vector<int>,int> temp2=findMinCost(coinDenoms,coinDenomSize,
coinCost,coinCostSize,amount-coinDenoms[coinDenomSize-1],limitPerDenomination-1);
if (temp1.second==-1&&temp2.second==-1)
return wrongpair;
else if (temp1.second==-1) {
temp2.first.push_back(coinCost[coinCostSize-1]);
temp2.second+=coinCost[coinCostSize-1];
return temp2;
}
else if (temp2.second==-1)
return temp1;
else {
temp2.first.push_back(coinCost[coinCostSize-1]);
temp2.second+=coinCost[coinCostSize-1];
return (temp1.second<temp2.second ? temp1:temp2);
}
}
Assume the return value is temp of type pair<vector<int>,int>.
Then, the findMinCost() array would be temp.first.
(Continued on next question...)
Other Interview Questions
| 