dynamic programming help

This is a discussion on dynamic programming help within the C++ Programming forums, part of the General Programming Boards category; hi all i need some help with this program. basically i have to create a text formatter like word or ...

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    6

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

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,663
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  2. dynamic array/vector help
    By Cpro in forum C++ Programming
    Replies: 8
    Last Post: 04-05-2008, 03:30 PM
  3. Identify dynamic IP address of network device
    By BobS0327 in forum Tech Board
    Replies: 2
    Last Post: 02-21-2006, 12:49 PM
  4. operator overloading and dynamic memory program
    By jlmac2001 in forum C++ Programming
    Replies: 3
    Last Post: 04-06-2003, 11:51 PM
  5. Dynamic memory confusion
    By ripper079 in forum C++ Programming
    Replies: 5
    Last Post: 11-04-2002, 05:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21