文本排版规划
问题描述：
输入n个单词，各单词长度分别为box[i].w（即每个单词的字母数，i=1…n）,单词为box[i].s。
struct BOX {
char s[Wp];//单词最大长度为15
int w;//单词长度
};
已知页面宽度为Wp（即该页每行容许的最大字母数）。要求输出每一行的单词分布。排版单词时，要求不改变各单词原来的顺序，且页面每一行各单词累加的长度不能超过页面宽度。 为了评价每行的排版美观程度，定义如下函数：
badness[i][j]=
当WL[i][j] > Wp,badness[i][j] = MAX
当WL[i][j] <= Wp,badness[i][j] = (Wp - WL[i][j])^3
其中，WL[i][j]表示第i个单词到第j个单词的累加宽度，Wp为页面宽度。该函数是每一行排版空白数的指标。函数取3次方，是为了增大差异值，凸显一行中存在空白的不美观程度。因此，可以认为badness越小越美观。
例如，页面宽度为20，有5个单词序列[good, good, good, good, good]，各个单词有4个字母，其宽度均为4。则：当一行中只有前2个单词时，badness(1,2) = (20-(4+4))3=1728；当一行中只有前3个单词时badness(1,3) = (20-(4+4+4))3=512；当一行中只有前四个单词时badness(1,4) =(20-(4+4+4+4))3=64。按照badness越小越美观的标准，显然一行中排前四个单词的方案优于前二者。
问题：
求解任意输入的n个单词的最优排版方案，要求单词之间最少应存在一个空格。
void main()
{
int n;
cout << "共有多少个单词：";
cin >> n;
BOX* box = CreateBox(n);
cout << "\n\n";
int** L = CreateWL_(n, box);
//int** L = CreateWL(n, box);
//1，2和3，4最优解不一定相同
//1，2两种方式最优解一定相同，但S不一定相同
if (1)
{
int** key = CreateKey(n);
short** s = CreateS(n);
long** badness = CreateBadness(n, L);
//long** badness = CreateBadness_(n, L);
RecurBest_u_d(badness, 1, n, s, key);
PrintfBest(box, 1, n, s);
}
if (2)
{
int** key = CreateKey(n);
short** s = CreateS(n);
long** badness = CreateBadness(n, L);
//long** badness = CreateBadness_(n, L);
CirculateBest_u_d(badness, 1, n, s);
PrintfBest(box, 1, n, s);
PrintfBadness(1, n, badness);
}
//3，4两种方式最优解一定相同，但S不一定相同
if (3)
{
int** key = CreateKey(n);
short** s = CreateS(n);
long** badness = CreateBadness(n, L);
//long** badness = CreateBadness_(n, L);
RecurBest_d_u(badness, 1, n, s, key);
PrintfBest(box, 1, n, s);
}
if (4)
{
int** key = CreateKey(n);
short** s = CreateS(n);
long** badness = CreateBadness(n, L);
//long** badness = CreateBadness_(n, L);
CirculateBest_d_u(badness, 1, n, s);
PrintfBest(box, 1, n, s);
}
system("pause");
/*PrintfL(1, n, L);
PrintfS(1, n, s);*/
}
测试例子：
//good book good book good book good book
//Do you like those people who always think of money and cannot remember the past
测试一截图：
测试二截图：
#include<iostream>
using namespace std;
#define Wp 16//该页每行容许的最大字母数
#define Max 10000000//无穷大
struct BOX {
char s[Wp];//单词最大长度为15
int w;//单词长度
};
BOX* CreateBox(int n);//记录单词信息矩阵
int** CreateKey(int n);//标记函数，所有元素初始化为0，当badness[i][j]已是最优值时将key[i][j]置为1
short** CreateS(int n);//划分矩阵
int** CreateWL(int n, BOX* box);//记录长度矩阵，未加空格,和CreateBadness_()配合使用
long** CreateBadness_(int n, int** L);//初始化美观程度评价矩阵，内部计算所需空格数并减去,和CreateWL()配合使用
int** CreateWL_(int n, BOX* box);//记录长度矩阵,在原来单词长度基础上加上一个空格的长度,和CreateBadness()配合使用
long** CreateBadness(int n, int** L);//初始化美观程度评价矩阵,和CreateWL_()配合使用
long RecurBest_d_u(long** badness, int i, int j, short** s, int** key);//自底向顶递归求最优值
void CirculateBest_d_u(long** badness, int set, int end, short** s);//自底向顶循环求最优值
long RecurBest_u_d(long** badness, int i, int j, short** s, int** key);//自顶向底递归求最优值
void CirculateBest_u_d(long** badness, int set, int end, short** s);//自顶向底循环求最优值
void PrintfS(int set, int end, short** s);//打印划分矩阵
void PrintfL(int set, int end, int** L);//打印单词长度
void PrintfBadness(int set, int end, long** badness);//打印美观程度评价矩阵
void PrintfBest(BOX* box, int set, int end, short** s);//打印最优排版
#include "All.h"
BOX* CreateBox(int n)//记录单词信息矩阵
{
int m = n + 1;
BOX* box = new BOX[m];
cout << "!!每个单词最大长度为15\n";
cout << "请按顺序输入每一个单词，单词之间用空格隔开！\n";
for (int i = 1; i < m; i++)
{
//cout << "第" << i << "个单词为：";
cin >> box[i].s;
box[i].w = strlen(box[i].s);
}
return box;
}
int** CreateKey(int n)//标记函数，所有元素初始化为0，当badness[i][j]已是最优值时将key[i][j]置为1
//当下一次需要获取badness[i][j]的最优值时，判断key[i][j]是否为1，是直接返回当前badness[i][j]；否计算最优值badness[i][j]
{
int m = n + 1;
int** key = new int* [m];
for (int i = 1; i < m; i++)
{
key[i] = new int[m];
for (int j = 1; j < m; j++)
key[i][j] = 0;
}
return key;
}
short** CreateS(int n)//划分矩阵
{
short m = n + 1;
short** s = new short* [m];
for (short i = 1; i < m; i++)
{
s[i] = new short[m];
for (short j = i; j < m; j++)
{
s[i][j] = -1;//在第i个单词后进行换行
}
}
return s;
}
int** CreateWL(int n, BOX* box)//记录长度矩阵，未加空格,CreateBadness_()配合使用
{
int m = n + 1;
int** L = new int* [m];
for (int i = 1; i < m; i++)
{
L[i] = new int[m];
L[i][i] = box[i].w;
}
for (int i = 1; i < m; i++)
{
for (int j = i + 1; j < m; j++)
{
L[i][j] = 0;
for (int k = i; k <= j; k++)
L[i][j] = L[i][j] + L[k][k];
}
}
return L;
}
long** CreateBadness_(int n, int** L)//初始化美观程度评价矩阵，内部计算所需空格数并减去,和CreateWL()配合使用
{
int m = n + 1;
int num;
long** badness = new long* [m];
for (int i = 1; i < m; i++)
{
badness[i] = new long[m];
for (int j = i; j < m; j++)
{
num = j - i;//需要添加的空格数
int overplus = Wp - L[i][j] - num;//空白数
if (overplus >= 0)
badness[i][j] = (overplus) * (overplus) * (overplus);
else
badness[i][j] = Max;
}
}
return badness;
}
int** CreateWL_(int n, BOX* box)//记录长度矩阵,在原来单词长度基础上加上一个空格的长度,和CreateBadness()配合使用
{
int m = n + 1;
int** _L = new int* [m];
for (int i = 1; i < m; i++)
{
_L[i] = new int[m];
_L[i][i] = box[i].w;
}
for (int i = 1; i < m; i++)
{
for (int j = i + 1; j < m; j++)
{
_L[i][j] = 0;
for (int k = i; k <= j; k++)
{
if (k < j)
{
_L[i][j] = _L[i][j] + _L[k][k] + 1;//多一个空格
}
else
_L[i][j] = _L[i][j] + _L[k][k];//最后一个单词不用加空格
}
}
}
return _L;
}
long** CreateBadness(int n, int** L)//初始化美观程度评价矩阵,和CreateWL_()配合使用
{
int m = n + 1;
long** badness = new long* [m];
for (int i = 1; i < m; i++)
{
badness[i] = new long[m];
for (int j = i; j < m; j++)
{
int overplus = Wp - L[i][j];//空白数
if (overplus >= 0)
badness[i][j] = (overplus) * (overplus) * (overplus);
else
badness[i][j] = Max;
}
}
return badness;
}
long RecurBest_d_u(long** badness, int i, int j, short** s, int** key)//自底向顶递归求最优值
{
if (i == j)
{
return badness[i][j];//只有一个单词，已是最优值
}
else
{
if (key[i][j] == 1)
return badness[i][j];//已有最优值，不需再递归计算
else
{
for (int k = i; k <= j - 1; k++)//从底向顶（1，2，……，n-1，n）
{
long m = RecurBest_d_u(badness, i, k, s, key) + RecurBest_d_u(badness, k + 1, j, s, key);
if (m < badness[i][j])
{
badness[i][j] = m;
s[i][j] = k;
}
}
key[i][j] = 1;
}
}
return badness[i][j];
}
void CirculateBest_d_u(long** badness, int set, int end, short** s)//自底向顶循环求最优值
{
for (int i = set; i < end; i++)
{
for (int j = i + 1; j <= end; j++)
{
for (int k = i; k <= j - 1; k++)//从底向顶（1，2，……，n-1，n）
{
long m = badness[i][k] + badness[k + 1][j];
if (m < badness[i][j])
{
badness[i][j] = m;
s[i][j] = k;
}
}
}
}
}
long RecurBest_u_d(long** badness, int i, int j, short** s, int** key)//自顶向底递归求最优值
{
if (i == j)
{
return badness[i][j];//只有一个单词，已是最优值
//s[i][i] = -1;
}
else
{
if (key[i][j] == 1)
return badness[i][j];//已有最优值，不需再递归计算
else
{
for (int k = j - 1; k >= i; k--)//从顶向底（n，n-1，……，2，1）
{
long m = RecurBest_u_d(badness, i, k, s, key) + RecurBest_u_d(badness, k + 1, j, s, key);
if (m < badness[i][j])
{
badness[i][j] = m;
s[i][j] = k;
}
}
key[i][j] = 1;
}
}
return badness[i][j];
}
void CirculateBest_u_d(long** badness, int set, int end, short** s)//自顶向底循环求最优值
{
for (int i = set; i < end; i++)
{
for (int j = i + 1; j <= end; j++)
{
for (int k = j - 1; k >= i; k--)//从顶向底（n，n-1，……，2，1）
{
long m = badness[i][k] + badness[k + 1][j];
if (m < badness[i][j])
{
badness[i][j] = m;
s[i][j] = k;
}
}
}
}
}
void PrintfS(int set, int end, short** s)
{
cout << "\n***************s[i][j]***************\n";
for (int i = set; i <= end; i++)
{
for (int j = i + 1; j <= end; j++)
{
cout << "s[" << i << "][" << j << "]=" << s[i][j] << "\t";
}
cout << "\n\n";
}
}
void PrintfL(int set, int end, int** L)
{
cout << "\n***************L[i][j]***************\n";
for (int i = set; i <= end; i++)
{
for (int j = i + 1; j <= end; j++)
{
cout << "L[" << i << "][" << j << "]=" << L[i][j] << "\t";
}
cout << "\n\n";
}
}
void PrintfBadness(int set, int end, long** badness)
{
cout << "\n***************badness[i][j]***************\n";
for (int i = set; i <= end; i++)
{
for (int j = i + 1; j <= end; j++)
{
cout << "badness[" << i << "][" << j << "]=" << badness[i][j] << "\t";
}
cout << "\n\n";
}
}
void PrintfBest(BOX* box, int set, int end, short** s)
{
int m = end - set + 1;
int i = set;
int j = end;
int t = 0;//共m个单词，每输出一个,t++
while (t <= m && s[i][j] != -1)
{
int k = j;
while (s[i][k] != -1)
{
k = s[i][k];
}
for (int w = i; w <= k; w++)
{
cout << box[w].s << "*";
t++;
}
cout << "\n";
i = k + 1;
}
if (t <= m)
{
for (int w = i; w <= j; w++)
{
cout << box[w].s << "*";
t++;
}
cout << "\n";
}
cout << "\n\n";
}
