首页 > 代码库 > 整齐打印
整齐打印
问题：
考虑整齐打印问题，即在打印机上用等宽字符打印一段文本。输入文本为n个单词的序列，单词长度分别为l1,l2,……,ln个字符。要求将此段文本整齐打印在若干行上，每行最多M个字符。若每行包含第i到底j(i<=j)个单词，且单词间隔为一个空格符，则行尾的额外空格符数量为M-j+i-(li+……+lj)，此值必须为非负的，否则一行内无法容纳这些单词。要求能最小化所有行（除最后一行）的额外空格数。
解决思路（转载）：由问题描述可知道，我们需要做的就是n个单词分成若干份，这与矩阵连乘问题有相似之处。行尾的额外空格符数量M-j+i-∑lk（i<=k<=j）可以看成M-（j-i）-∑lk，其中j-i是表示该行各个单词之间相隔的空格数量。我们设lc[i,j]是第i个单词到第j个单词的额外空格符数量的立方，即是（M-j+i-∑lk)3（i<=k<=j),则有已下公式：
lc[i,j]=∞，当M-j+i-∑lk<0 (i<=k<=j)；lc[i,j]=0,当M-j+i-∑lk>=0 (i<=k<=j),且j==n；lc[i,j]=（M-j+i-∑lk)3，当当M-j+i-∑lk>=0 (i<=k<=j),且j!=n。公式解析：当M-j+i-∑lk<0时，说明第i个单词到第j个单词被划作成一行的时候，各单词以空格相隔后，其字符数量已经超出了M，也就是说不应该把第i个单词到第j个单词作为一行，因此设其lc值为无穷大。若当j==n时，证明第i个单词到第j个单词所划分成的一行是最后一行，所以根据题目意思，其lc值为0。除去以上两种情况，lc值按照额外空格数的立方进行计算。
根据动态规划的思想，必须找到问题的最优子结构性质，我们将第i，i+1...j个单词一字排开，每次选择一个位置k将一行划分出来，假设我们从这堆单词后面开始，也就是选定第k个单词到第j个单词作为一行，使得其在完成结合往后的选择然后所有行的（除最后一行外）额外空格数的立方之和最小，剩下子问题，需要对第i，i+1...k-1个单词选择一个最优位置进行划分。于是我们设c[j]是从第i个单词开始到第j个单词结束的序列的在划分成若干行后各行额外空格数的立方之和。（可以看到我们并没有设成是c[i,j],那是因为自始至终，原问题和子问题中的单词序列都是以i开始的，当然，当我们在实际实现的时候，尤其是在使用自底向上的方法的时候（也就是首先计算出原问题最小的子问题，然后再计算更大的子问题直到原问题的方法），我们要解决的是第1,2,3...n个单词的序列，当然要从计算c[1]开始。）
c[j]的计算公式如下：
c[j]=0,当j=0；c[j]=min {c[k-1] + lc[k,j] }(1<=k<=j),当j>0；显然，当j=时，即是输入的序列为空，那么问题将没意义，故设为0；当j>0时，选择第k...j个单词组成一行，给k值是从1到j之间寻找，类似于矩阵连成找k值的情况，此时子问题第1...k-1个单词的最优值加上选择第k...j个单词组成一行的额外空格符数量的立方，便组成了原问题的解。于是，我们便递归的定义了该问题的最优解。
原文出处：http://1439154.blog.51cto.com/1429154/1190038
// zhengqidayin.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
using namespace std;
#include <time.h>
#define M 50 //每行最多M个字符
#define N 50 //单词个数
#define Inf 65536 //无穷大
int lc[N + 1][N + 1]; //第i个单词到第J个单词空格数的立方
int l[N + 1]; //每个单词的长度
int c[N + 1]; //存放第1个单词到第i个单词最优时的立方空格数和
int r[N + 1]; //用于存放最优解
int RANDOM(int p, int r) //用于产生随机数
{
srand((unsigned)time(NULL));
return (rand() % (r - p + 1)) + p;
}
void cal_lc() //计算所有当第i个单词和第j个单词放在同一行上时额外的空格数
{
for (int i = 1; i <= N; i++)
{
for (int j = i; j <= N; j++)
{
int word_length = 0;
for (int k = i; k <= j; k++)
word_length += l[k];
int blank = M - j + i - word_length;
if (blank < 0) //说明第i到第j个单词不能放在同一行上
lc[i][j] = Inf;
else if (j == N) //说明为最后一行，不计入空格数
lc[i][j] = 0;
else if (blank >= 0)
lc[i][j] = blank*blank*blank;
}
}
}
void result()
{
c[0] = 0;
cal_lc();
for (int j = 1; j <= N; j++)
{
c[j] = c[0] + lc[1][j];
r[j] = 1;
for (int k = 1; k <= j; k++) //此循环求递归式min
{
int q = c[k - 1] + lc[k][j];
if (q<c[j])
{
c[j] = q;
r[j] = k; //某行以k为起点，j为终点
}
}
}
}
int print(int j)
{
int i = r[j]; //得到起点，j为终点
int num;
if (i == 1) num = 1;
else
num = print(i - 1) + 1; //i-1为上一行的末尾
cout << num << ‘\t‘ << i << "\t\t"<< j << endl;
return num;
}
int main()
{
for (int i = 1; i <= N; i++)
l[i] = RANDOM(3, 3+i%11);
cout << "给定各单词长度：" << endl;
for (int i = 1,k=0; i <= N; i++)
{
k++;
cout << l[i] << ‘\t‘;
if (k % 5 == 0)cout << endl;
}
cout << endl<<"行号\t起始单词\t结束单词" << endl;
result();
print(N);
while (1);
return 0;
}
整齐打印