### Dynamic Programming Coin Change Problem

I am having an issue with my coin change program. The idea behind the program is to take input from a text file which will be coin values and an amount and fine the lowest number of coins of the given domination to make that amount. For example:
1 2 5
10
1 3 7 12
29

This would return the following in a text file:
1 2 5
10
0 0 2
2
1 3 7 12
29
0 1 2 1
4

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242`` `````` #include #include #include #include #include #include using namespace std; //function to convert string to int vector vector list_from_string(string len) { string x = ""; vector vec; for (int i = 0; i <= len.length(); i++) { if (i == len.length() || len[i] == ' ') { //stoi function used to convert string to int vec.push_back(stoi(x)); x = ""; } else { //appending chars to string x = x + len[i]; } } return vec; } //function to calculate change from denom and coins vector calculate(vector denom, int coins) { //creating a 2d bool array bool arr[coins + 1][denom.size() + 1]; //issue here //setting all values to false for (int i = 0; i <= coins; i++) { for (int j = 0; j <= denom.size(); j++) { arr[i][j] = false; } } //setting values with 0 coins to true for (int i = 0; i <= denom.size(); i++) { arr[0][i] = true; } //filling array using dynamic programming for (int i = 1; i <= coins; i++) { for (int j = 1; j <= denom.size(); j++) { if (i >= denom[j - 1]) { arr[i][j] = arr[i][j] || arr[i - denom[j - 1]][j] || arr[i - denom[j - 1]][j - 1]; } } } int x = coins; int y = denom.size(); //creating resulting vector vector ans; for (int i = 0; i0 && y>0) { if (arr[x - denom[y - 1]][y]) { ans[y - 1]++; x = x - denom[y - 1]; } else if (arr[x - denom[y - 1]][y - 1]) { ans[y - 1]++; x = x - denom[y - 1]; y--; } else { y--; } } //returning the vector return ans; } int main() { //ifstream object to read amount.txt to take as input ifstream infile("amount.txt"); string str; //denom vector to store denominators in a vector vector denom; //a flag variable to read denominators first then coins second. int flag = 0; //ofstream object to write output to change.txt ofstream myfile; myfile.open("change.txt"); //while loop to read lines of amount.txt while (getline(infile, str)) { //if flag is 0 then denominators are read //else if flag is 1 then no of coins are read if (flag == 0) { //function to convert string to int vector denom = list_from_string(str); //writing vector to change.txt file for (int i = 0; i change = calculate(denom, coins); //writing change vector to change.txt file and calculating no of coins int no = 0; for (int i = 0; i

When I go to try and make a 2D array of bools using this: bool arr[coins + 1][denom.size() + 1], my IDE is causing an error to be thrown. Any advice or guidance would be appreciated.
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102`` ``````#include #include #include //function to convert string to int vector std::vector list_from_string(const std::string& list); //function to calculate change from denom and coins std::vector calculate(const std::vector& denom, int amount); int main() { std::ifstream infile("amount.txt"); bool flag { true }; // denominations first, then amount. std::ofstream outfile("change.txt"); std::vector denom; // denominations (must endure two iterations!) for (std::string str; getline(infile, str); /**/) { if (flag) { denom = list_from_string(str); for (std::size_t i = 0; i < denom.size(); i++) { outfile << denom.at(i) << ' '; } outfile << '\n'; flag = false; // at next iteration read the amount! } else { int amount = std::stoi(str); outfile << amount << '\n'; std::vector change = calculate(denom, amount); int no = 0; for (std::size_t i = 0; i list_from_string(const std::string& list) { std::string x; std::vector vec; for (std::size_t i = 0; i <= list.length(); i++) { if (i == list.length() || list.at(i) == ' ') { vec.push_back(std::stoi(x)); x.clear(); } else { x += list.at(i); } } return vec; } std::vector calculate(const std::vector& denom, int coins) { bool** arr = new bool*[coins + 1]; for(int i {}; i < coins + 1; ++i) { arr[i] = new bool[denom.size() + 1] { false }; } //setting values with 0 coins to true for (std::size_t i = 0; i <= denom.size(); i++) { arr[0][i] = true; } //filling array using dynamic programming for (int i = 1; i <= coins; i++) { for (std::size_t j = 1; j <= denom.size(); j++) { if (i >= denom[j - 1]) { arr[i][j] = arr[i][j] || arr[i - denom[j - 1]][j] || arr[i - denom[j - 1]][j - 1]; } } } int x = coins, y = denom.size(); //creating resulting vector std::vector ans (denom.size()); //filling vector using backtracking while (x > 0 && y > 0) { if (arr[x - denom[y - 1]][y]) { ans[y - 1]++; x = x - denom[y - 1]; } else if (arr[x - denom[y - 1]][y - 1]) { ans[y - 1]++; x = x - denom[y - 1]; y--; } else { y--; } } for(int i {}; i < coins + 1; ++i) { delete[] arr[i]; } delete[] arr; return ans; }``````

Topic archived. No new replies allowed.