문장이 가득 쓰여진 엑셀이란?

이런 느낌의 것입니다. 셀 내에서 문자가 줄 바꿈되어 있네요.
두 테이블의 가로 폭은 동일하지만 높이는 다릅니다.
오른쪽의 표는 「타.」만의 행이 있거나 해 낭비로 높이를 벌어 버리고 있군요.
왠지 이것이 싫었기 때문에 열폭을 조정하거나 하고 있었습니다만, 엔지니어라면 합리적으로 폭을 산출해야 하지 않을까 생각합니다.

수식으로 표현하면 어떻게 될까요?

행 $i$, 열 $j$, 각 열의 폭 $w_j$, 각 셀의 문자수 $s_{ij}$ 로 한다.
표의 폭은 $W$로 고정되어 있다고 한다.
셀의 문자열에는 개행 문자가 포함되어 있지 않습니다. (문제가 어려워지기 때문에)
또한, 등폭 폰트를 사용해, $w_j$는 「1행에 늘어놓을 수 있는 문자수」로 나타낸다.
폭은 1 이상의 정수로 한다.

높이 계산

예를 들면 80문자 셀이 열폭 9문자라면 「80/9=8행 너무 8문자」로 반올림해 9행입니다.
각 셀의 높이 $h_{ij} = {\rm ceiling}(s_{ij}/w_j)$ 로 나타냅니다.
또, 행 $i$의 높이는, 결국 옆에 있는 동행 셀중에서 제일 높은 것이 됩니다.
$i$ 행의 높이 $h_i={\rm max}(h_{i1}, h_{i2}, ..., h_{iJ})$ 로 표시합니다.
최종 테이블의 높이 $h$는 각 행의 높이의 합입니다. 이것을 최소화하고 싶습니다.

제약

각 열폭의 합은 표폭이 된다. $\sum w_j = W$
열폭은 1 이상이 된다. $w\ge 1 , w\in {\mathbf w}$

한 줄만의 표를 예로 생각

이것이라면 다른 행과의 합의를 생각하지 않아도 좋기 때문에 편하네요.
표폭 $W=20$, 3열로 문자수는 각각 $s_1 = 5$, $s_2 = 30$, $s_3 = 50$
라는 예로 생각해 보겠습니다.
${\mathbf w} = (1,1,18)$에서 ${\mathbf w} = (18,1,1)$까지 $18^3=5832$개보다는 적은 조합이 생각됩니다. 절대 좋은 해법은 아니지만, 시라미트부시에 찾아 보겠습니다.

간단한 예제의 최적 솔루션을 무리하게 계산하기 (PowerShell)

$W = 20  # 表幅
$s = (5,30,50)  # 各セルの文字数
$ans = (1,1,18) # 数値に意味はない

$minHeight = 51 # これより悪くはならないという初期値
$minAns = (1,1,18) # 無作為な初期解

function calcH($s, $w){ [Math]::Ceiling($s/$w) } # 0除算はエラーを出す

for($k=1; $k -le 18; $k++){
  for($l=1; $l -le 18; $l++){
    for($m=1; $m -le 18; $m++){
      if($k+$l+$m -ne $W){ continue } # 「各列幅の総和は表幅と等しい」制約
      $ans=($k, $l, $m)
      $h1 = calcH $s[0] $k
      $h2 = calcH $s[1] $l
      $h3 = calcH $s[2] $m
      $height = ($h1,$h2,$h3 | Measure-Object -Maximum).Maximum

      if($height -lt $minHeight){
        $minHeight = $height
        $minAns = $ans
      }

      echo ("("+ ($ans -join ',') +")=>" + $height + " ==max(" + $h1+","+$h2+","+$h3 + ")") >> min_table_height.log
    }
  }
}
echo ("min height is " + $minHeight + " at " + ($minAns -join ',')) >> min_table_height.log

전체 171 패턴의 최적해는 (1,6,13), 높이는 5행이었습니다.

보다 간단하게 결과를 그래프로 표시

표폭 $W=20$, 2열로 문자수는 $s_1 = 30$, $s_2 = 50$로 했을 경우,
전체 19 패턴의 최적해는 (6,14)로 높이는 5행이 됩니다.
첫 번째 열의 열 너비와 행 높이 사이의 관계는 아래 그래프와 같습니다.

열 1의 폭이 너무 좁은 최초의 쪽은 $y=30/x$같은 그래프로, 반대로 마지막 쪽은 $y=50/(20-x)$같아지고 있네요.
「시」형의 함수와, 좌우 반전한 「시」형 함수가 부딪치고 있는 느낌입니다.
3차원(3열)이 되면 이것의 중간에 막대기를 찔러서 돌린 것 같은 그래프가 될 것 같습니다. 최악의 경우, 계란의 팩 같은 국소해가 흩어진 도형이 되기도 합니다.

어땠어?

테이블을 세로로 컴팩트하게 만드는 열 너비를 찾았습니다. 어쩐지 어려울 것 같았기 때문에 전제를 두고, 가장 간단한 케이스를 총당으로 풀어 보았습니다. 결과, 그렇게 복잡한 해공간이 아닌 것 같은 생각이 들었습니다. 그렇다면 가장 간단한 케이스를 풀었으니까 그럴 것이라고 생각합니다. 그렇지만, 「다른 행과의 합쳐」라고 하는 요소가 더해져도, 그렇게 복잡하게는 되지 않을까요 모르겠습니다.
여기까지 겨우 하고 있습니다만, 메타휴리스틱 수법으로 해결하는 것 같은 오치가 된다고 생각합니다. 문제에 대해 생각해 보았지만 능숙하게 정식화할 수 없기 때문에 휴리스틱 수법으로 해결하는 것은 전혀 합리적이지 않다고 생각하네요.
교과서에 실려 있는 연습 문제는 풀 수 있는데 응용적인 문장제를 내면 풀 수 없는 우등생 같은 기분이 되었습니다만, 애초에 교과서의 문제를 풀었던 적이 없었습니다. 정진합니다.