漂亮列印問題與動規模型的建立

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