C++ please help I will give you a good rating!!!!!
Implement the following function by using subsets() developed in step 1.
/* Check if given value given be expressed by K or less coins chosen from the given set of coins
@param coins: all coins we can choose from
@param first, last: specify the range of coins to choose from, i.e., coins[first…last]
@param value: the value to express
@param K: the maximum # of coins to use
@precondition: all coins have positive values
@postcondition: return true of false depending on the checking result */
bool CoinChangeK (const vector & coins, int first, int last, int value, int K)
Hint: call subsets( ) function to return all possible subsets, and then go through them to see if any subsets with size <=k as="" a="" sum="" equal="" to="" value="" or="">
CODE
#include
#include
#include
using namespace std;
void PrintVector (const vector & v){
cout <>
for (auto e:v){
cout<><">
}
cout <>
}
/* check if we can use values in L[left...right] to make a sum of value, and find
the best solution, i.e., smallest set of coins tht make this value
@param L, first, last: specify a sub-vector where coins/values are chosen from
@param value: the sum/value we want to make
@pre-condition: all parameters are initialized, L[] and value are non-negative
@post-condition: return true/false depending on the checking result, if return true,
used vector contains coins that make up the value, with the minimul # of elements from
L [first...last]
*/
bool CoinChange (vector & L, int first, int last, int value, vector & used)
{
if (value==0)
{
used.clear();
return true;
}
if (first>last) //no more coins to use
{
used.clear();
return false;
}
if (value<>
{
used.clear();
return false;
}
//general case below
vector used1;
bool ret1= CoinChange (L, first, last-1, value-L[last], used1);
if (ret1)
// used1 include all values from L[first...last-1] that add up to valeu-L[last]
used1.push_back (L[last]);
//now: used1 include all coins used from L[first...last} that add up to value
vector used2;
// If not using L[last]...
bool ret2 = CoinChange (L, first, last-1, value, used2);
if (ret1 && ret2) {
if (used1.size() > used2.size())
used = used2;
else
used = used1;
return true;
} else if (ret1) {
used = used1;
return true;
} else if (ret2){
used = used2;
return true;
} else {
used.clear();
return false;
}
}
bool CoinChangeK (const vector & coins, int first, int last, int value, int K)
{
return true;
}
bool UnlimitedCoinChange (const vector & coins, int value, vector& bestSolution)
{
return true;
}
int main()
{
vector coins{2,5,3,10};
vector used;
vector values{4, 6,15, 18, 30, 41}; //use this to test
//This part demo the CoinChange function: optimization problem
/*
for (auto v: values) {
//Todo: replace CoinChange with your CoinChangeUnlimited function...
if (CoinChange (coins, 0, coins.size()-1, v, used))
{
cout <><">
//display used vector
for (int i=0;i<>
cout <><">
cout<>
}
else
cout <"value="><><"><>
}
*/
//Test CoinChangeK
cout <"enter coinchangek="" or="" unlimited="" to="" test="" the="" corresponding="">
string command;
cin >> command;
if (command=="coinchangek"){
//we cannot make 20 using 2 or fewer coins
if (CoinChangeK (coins, 0, coins.size()-1, 20, 2)!=false ||
CoinChangeK (coins, 0, coins.size()-1, 5, 1)!=true)
{
cout <"fail coinchangek="">
return 1; //faild coinchangeK test
}
else{
cout <"pass coinchangek="">
return 0; //pass coinchangeK test
}
} else if (command=="unlimited"){
//Test UnlimitedCoinChange
vector bestSolution;
if (UnlimitedCoinChange (coins, 1,bestSolution)!=false) {
cout <"failed unlimitedcoinchange="" case="">
return 1; //failed unlimited test
}
if (UnlimitedCoinChange (coins, 15, bestSolution)!=true) {
cout <"failed unlimitedcoinchange="" case="">
return 1;
}
vector expectedSol{5,10};
sort (bestSolution.begin(), bestSolution.end());
if (bestSolution!=expectedSol){
cout <"failed unlimitedcoinchange="" case="">
return 1;
}
if (UnlimitedCoinChange (coins, 30, bestSolution)!=true) {
cout <"failed unlimitedcoinchange="" case="">
return 1;
}
vector expectedSol3{10,10,10};
sort (bestSolution.begin(), bestSolution.end());
if (bestSolution!=expectedSol3){
cout <"failed unlimitedcoinchange="" case="">
return 1;
}
cout <"pass unlimitedcoinchange="">
return 0;
}
}