Write a C++ program that can solve problem 14-4 from the end of chapter 14 via dynamic programming. I have very specific requirements for the code you should write. Please make sure that you follow all of the requirements listed below.
When your program starts up it will read a list of words from a text file. The program will then prompt the user to enter a maximum line width to use when breaking the text into lines. The program will then compute the optimal way to arrange the text into lines whose width stays within that maximum width limit and then print the text with the line breaks at the optimal locations.
Start by declaring three global vectors:
vector<std::string> words; vector<int> wordLengths; vector<vector<int> > linePenalties;
The words vector is the list of words that you need to lay out into lines. The wordLengths vector stores the length of each word. The linePenalties array stores precomputed penalties for all possible line configurations. For example, linePenalties[n][k] stores the end of line penalty you would incur if you put k+1 words on a line starting with word n. Note that a line of text that starts at word n has a maximum number for words that will fit on that line. You only need to compute penalties for every possible number of words on that line up through the maximum. That maximum will most likely differ for different values of n, so not every row in the linePenalties vector will have the same length.
You should write and use an initialization function that reads the words from the text file and initializes these three vectors from that data.
To solve the main problem, I am going to require you to start by writing the code for a recursive function
int minPenalty(int n)
that can compute the lowest possible total penalty you can achieve when laying out words n..N, where N is the total number of words in your text. I only want you to write the code for this function to demonstrate that you know how to do it. Since this recursive calculation is far too slow, you should not actually call this function in your program. Instead, you will use the logic you set up in the recursive version as a starting point and then generate a dynamic programming solution from it. You should use the data in the linePenalties vector to help you implement the logic both in the recursive solution and in the dynamic programming solution.
For the dynamic programming solution you need to set up two one-dimensional tables. One table will store the minimum penalty for laying out words n through N, while the other will store the optimal number of words to put on a line that starts with word n.
As the textbook says, the penalty for each line in the text is the cube of the number of spaces left over at the end of the line. If you have stored the number of spaces left at the end of a line in a variable spaces, please do not try to compute this penalty by doing
spaces^3
The ^ operator in C++ is not the exponentiation operator, it is the exclusive or operator. Instead, compute the cube by doing
spaces*spaces*spaces
Also, don't forget to remember the special rule that says penalties for extra spaces at the end of a line apply to all lines in the text except for the very last line. One consequence of this rule is that if the words n through N will all fit on a single line, then every entry in the row linePenalties[n] will be 0. Likewise, if words n through N all fit on a single line then minPenalty(n) should return 0.