Thread: dynamic programming help

hi all
i need some help with this program.
basically i have to create a text formatter like word or TeX.
given a block of text i have to insert line breaks so that each line of the text will fit within a certain width.
so for each line i have to associate a penalty
so..
penalty = (text_width - linesize)^3
what i need to do is given an unformatted text and a desired width find a way to compute the formatting that minimizes the penalty
heres what i have so far. a lot of it is just ideas when i run it it does nothing.....

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
//
//vector<string>
string format_paragraph( vector<string> words, int
text_width) {
  int i,j,n,space;
  
   
  n = words.size();
  
  //vector< vector<int> >length (n,n);
  int length[n];
  //for(i = 0; i < n; ++i){
  //length[i] = words[i];
    //for(j=i+1; j<n; ++j)
    //length[i][j] = length[i][j-1] + 1;
    //    }
            
//vector< vector<int> >penalty (n,n);
int penalty[n];    
for( i=0; i<n; ++i){
    //for( j = i; j < n; ++j){
        if(length[i] < text_width)
        penalty[i] = (text_width - length[i])^3;
        else 
        penalty[i] = INT_INFINITY;    
        
      }
    //int n = words.size(); 
//vector< vector<int> >cost (n,n);
int cost[n];
for(int i = 0; i < n; ++i){
cost[i] = penalty[i];// could be segfault
    for( i = i - 1; i >= 0; --i){
    int min = penalty[i];
        for(int k = i; k < n; ++k){
        int temp = penalty[i] + cost[i+1];
        if(temp<min)
        min=temp;
        }
        
    cost[i] = min;
    
    }
  }    
}    
    

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;
  }
}