漂亮打印问题与动规模型的建立

转自http://blog.csdn.net/petercsj/article/details/4571400

这是算法导论动态规划一章的课后思考题

题目如下：

    由给定的n个英文单词组成一篇文章，每个单词的长度(字符个数)依次为l1,l2...要在一台打印机上将这段文章漂亮的打印出来．打印机每行最多可打印Ｍ个字符．这里说说的漂亮定义如下：在打印机所打印的每一行中，行首和行尾可不留空格；行中每两个单词之间可留一个空格；如果在一行中打印从单词i到单词j的字符，则按照打印规则，应该在一行中打印sum(li,i<=i<j)+j-i个字符，且不允许将单词打破多余的空格数为Ｍ-j+i-sum(li,i<=i<j);除文章的最后一行外，希望每行多余的空格数目尽可能少，以每行多余空格数的立方和达到最小作为漂亮的标准（最后一行不算）．

比如M=5

         a︻bc︻

         d︻ef︻

         g（最后一行不算）

︻表示空格  总空余为1*1*1+1*1*1=2

         最近一直在研究动规方面的问题，看到这道题后略一思索便想出了该问题的最优子结构：最后一行必定是从i到n,当然i必须在能够打印的范围内。i定下来之后，前面的段落必定是最小和，否则必定能找到一个更优解。这样不断迭代到初始情况，便可解决问题。

         找到最优子问题结构只是动规的第一步。接下来还剩下一些问题：

（1）状态变量如何表示？？一维？二维？？

（2）边界情况如何处理。

                   一、最后一行不算，应该如何处理？

                   二、每一行是否超出最大字符数如何判断？

                   三、初始状态怎么处理？

         先来看状态变量。刚一开始可能会想到用二维DP。但仔细想过后发现无法实现。于是转向一维，我们以数组c[j]表示以第j个元素结尾的段落，且第j+1个另起一行。这样便写出了状态转移方程c[j]=max{c[i-1]+lc(i,j)} (1<=i<=j),其中lc(i,j)表示以i起头，以j结尾的一行。这样便刻画出了我们一开始想到的最优子结构！

         接下来是边界处理。我们假设数据下标从1开始。那么可取c[0]=0，如果取c[0]作为次状态，那么表示当前状态处在第一行。比如，c[1]=c[0]+lc(1,1)=l1。然后我本来准备进行判断，如果i到j超过规定字符，则i++。然后如果j=n，并且i到j在规定字符内，c[j]=max{c[i-1]};

(1<=i<=j)。那么状态转移就变成了

                   （1）max{c[i-1]+lc(i,j)} (1<=i<=j&&lc(I,j)<=M)    //正常情况

         c[j]= （2）c[i-1]                         (j=n&&1<=i<=j&&lc(I,j)<=M)            //最后一行

这样实现起来要加上许多判断，就显得很繁琐。

         导论上的方法是，令lc()的返回值有三种状态：正常，0，无穷。这样只需一个状态转移c[j]=max{c[i-1]+lc(i,j)} (1<=i<=j),并且自动过滤掉了边界情况，漂亮！

         至此问题已全部解决，可以开始写代码了。从这个例子可以看出，DP的边界情况处理是非常重要的。我们的解题顺序大致是：刻画最优子结构à刻画状态变量à考虑边界情况à写代码。本人也是初学DP不久，只是写一写自己的思考，欢迎高手指正J

源代码：

#include<iostream>
using namespace std;
int m,n;    //每行最大容量
int c[1000];       //状态数组
int l[1000];       
int p[1000];      //保存记录用于重构最优解的数组
 
//lc函数用来分类，把边界情况考虑进去，好想法！！！
int lc(int i,int j) {                          
         int temp=0;
         for(int k=i;k<=j;k++)
                   temp+=l[k];
         int s=m-j+i-temp;
         if(s<0)       return 10000000;    //从i到j的单词不能放在一行
         if(j==n)      return 0;           //最后一行
         else  return s*s*s;
 
}
void PrettyPainting()        {
         c[0]=0;                        //base case;
         int min;
         for(int j=1;j<=n;j++) {
                   c[j]=100000000;
                   for(int i=1;i<=j;i++)
                            if(c[i-1]+lc(i,j)<c[j])             {c[j]=c[i-1]+lc(i,j);p[j]=i;}
         }
         cout<<c[n];
}
 
int main()
{
         cin>>m>>n;
         for(int i=1;i<=n;i++)
                   cin>>l[i];
         PrettyPainting();
         return 0;
}