Algorithms CoinChange

Requirements:
1. Implement the following function that returns a vector of vectors of Item, each of which is a subset of elements chosen from the given vector a[first…last]:
/* if a is {1,2,3}, first=0, last=2, the function shall returns a vector of the following vectors: {}, {1}, {2}, {3}, {1,2},{1,3}, {2,3},{1,2,3}, all subsets of a[0…2].
Precondition: last-first+1>=1, i.e., there is at least one element in the a[first…last]
Note 1)if the length of a[first…last] is n, then the function should return a vector of 2n vectors
2) The order of these subsets does not need to match what’s listed here… */
vector> subsets (const vector & a, int first, int last)
Note: Please refer to the examples in the slides…
2. 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 not. 3. Implement an unlimited coin change problem, where each coin can be used for an unlimited number of times. /* Check if given value given be expressed by coins chosen from the given set of coins @param coins: all coins we can choose from @param value: the value to express @precondition: all coins have positive values @postcondition: return true or false depending on the checking result, if return true, bestSolution is set to include the solution that uses minimum number of coins */ bool UnlimitedCoinChange(const vector & coins, int value，vector & bestSolution) Implement this function recursively, based upon the logic learnt in class (i.e., use decision tree to guide
your design of the recursive algorithm).

Code:
#include
#include
using namespace std;
// Todo1: Add cout statement to MergeSort () to print out
// a line for each time this function is called, show the parameter
// a line for each time we return from this function, show the parameter
// format: MergeSort called, parameter=[2,8,1,7]
// MergeSort returned, parameter=[1,2,7,8]
//Todo2: Implement Q5 (a) following the following steps
// 1) Modify ALL comments as needed,
// 2) Modify BinaryMergeSortedList() based upon the updated comments
// i.e., to merge l1, l2, both already in descending order, into list
// so that list will be in descending order
/* Merge two sorted vectors’ elements into one sorted vector
@param l1, l2: two sorted vectors
@param list: the vector to hold the merging result
@pre-condcition: elements in l1, l2 are in ascending order
@post-condcition: list contains elements from l1 and l2, in ascending order */
void BinaryMergeSortedList (const vector l1, const vector l2, vector & list)
{
//Idea: as well as l1 and l2 both have elements left to be copied to list,
// compare the “front runner”, and copy the smaller one to next slot in list.
// When only one of l1, l2 have elements left, copy all remaining elements to list
// one by one.
//make sure list has exact same # of elements as l1, l2 combined:
// (by dropping extra or adding 0 to the end)
// subsequently, we can use list[k] or list.at(k) to refer to each element…
// more efficient than:
// 1) first: list.clear(); //make list an empty list
// 2) and then: list.push_back(l1[i++]); //to add a new element into
// the back (end of list).
list.resize(l1.size()+l2.size());
int i,j,k; //used to index l1, l2 and list respectively
i=j=k=0; //start from first position
while (i
if (l1[i] <= l2[j]) //comparison operation //copy smaller one to list, and advance indices list[k++] = l1[i++]; //copy operation else list[k++] = l2[j++]; //copy operation } //copy remaining elements to list while (i list[k++] = l1[i++]; //copy operation while (j list[k++] = l2[j++]; //copy operation } /* sort the vector into ascending order @param list: the vector of int to be sorted @pre-condiction: list has been initialized with some data @post-condition: the integers stored in list are rearranged into ascending order */ void MergeSort (vector & list)
{
//base case 1
if (list.size()==1)
return;
//Todo3: Add a base case for the case when list contains two elements
// only
//Todo4: Add a third base case: when list’s length is less than
// 50, call insertion sort (from your lab2), or bubblesort (from your
// lab1) to sort it
//general case: divide and conquer
//divide part
int n=list.size();
int mid = (0+n-1)/2; //averge of first and last index
vector leftHalf(list.begin(),list.begin()+mid+1);
// range constructor: initilize with elements from a range of existing vector:
// from first iterator (including) to last iterator (not included)
//https://www.cplusplus.com/reference/vector/vector/vector/
vector rightHalf(list.begin()+mid+1,list.end());
//conquer part: solve the two subproblems recursively (and independently from
// each other
MergeSort (leftHalf);
MergeSort (rightHalf);
//Combine part: merge data from the two sorted halves
// back into list, in ascending order
BinaryMergeSortedList (leftHalf, rightHalf, list);
}
int main()
{
vector a{6,4,3,8,2,5,1,7};
MergeSort (a);
cout<<"result:"; //use iterator to go through vector a //for (vector::iterator it=a.begin(); it //cout <<*it <<" "; for (auto element:a) //supported in C++11, element's type is auto cout < cout < //Todo 5: // Generate random vector of size of length n=500 }

Last Completed Projects