hi all
im having a probe creating this algorithm:
i need to create a dynamic algorithm, the one below the greedy one, to formate text. everything i need is here but i cant figure out how to compute the line_cost and store it into an array
any ideas?
thanx
Code:
#include <iostream>
#include <vector>
#include <string>
//////////////////////////////////////////////////////
///
/// Usage:
///
/// format_text text_width
///
/// reads lines of text on standard input, then
/// prints the text, formatted, on standard output.
///
/// line breaking is done to minimize a penalty
function.
///
//////////////////////////////////////////////////////
#include "sprint.h"
using std::vector;
using std::map;
using std::string;
using std::cout;
using std::cerr;
using std::cin;
using std::endl;
#define DEFAULT_TEXT_WIDTH 60
#define INT_INFINITY (1<<30)
#define MIN(a,b) ((a)<(b)?(a):(b))
// trim trailing blanks from a given string
void
trim(string& s) {
int i = s.size()-1;
while (i >= 0 && s[i] == ' ')
--i;
s.erase(i+1);
}
// return the penalty associated with a given line
int line_cost(string line, int text_width) {
trim(line);
int gap = text_width - line.size();
if (gap < 0) return 1000000;
return gap*gap*gap;
}
//
// given a sequence of n words, and integer text_width
//
// find the minimum total penalty possible for
// any formatting of words[0], words[1], ...,words[n-1]
//
// return the formatted text as a string
//
string format_paragraph( vector<string> words, int
text_width) {
//this is the greedy algorithm
/*string output = "";
int length=0;
for (int i=0; i < words.size(); ++i) {
if (length > 0 && length + words[i].size() >
text_width) {
output += "\n";
length = 0;
}
output += words[i] + " ";
length += words[i].size() + 1;
}
if (length > 0) output += "\n";
return output;*/
// this is the dynamic algorithm
int last = (int)words.size()-1;
for(int i=last; i>=0;i--){}
}
int main(int argc, char *argv[]) {
int text_width = DEFAULT_TEXT_WIDTH;
if (argc >= 2) {
text_width = atoi(argv[1]);
}
// read, format, and output a sequence of paragraphs
// (new paragraph starts with a word "<p>")
while (std::cin) {
// get paragraph
vector<string> words;
while (std::cin) {
string word;
std::cin >> word;
if (word.empty()) break;
if (word == "<p>") break;
words.push_back(word);
}
// output paragraph, formatted
if (words.empty()) continue;
cout << format_paragraph(words, text_width);
cout << endl;
}
}