dynamic programming help

[twigboy]

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.....

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

[Salem]

> penalty[i] = (text_width - length[i])^3;
^ isn't raise-power in C or C++, it's the bitwise-exclusive-or operator.

> for(int i = 0; i < n; ++i){
>cost[i] = penalty[i];// could be segfault
> for( i = i - 1; i >= 0; --i){
Using the same index variable for two different loops is a sure loser

Also, you might want to work on your indentation a little, the code is kind of hard to follow even though youv'e used code tags ( which is good )
Removing all your comments containing code you've tried would also help us to focus on the specific issue at hand.

[okinrus]

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.....

Trigboy, I'm not sure how your solving the problem, and why your using a trim function. I'd rewrite the algorithm to a recursive solution, and then transform the recursive solution into dynamic solution using arrays. Test this on paper, and you should then procede to code. You should be able to clearly see where your code doesn't match with your paper if you do this correctly.