表全体の高さが最小になるような各列の幅の組合せを見つけたい(調査編)

文章がいっぱい書いてあるエクセルとは

こんな感じのものです。セル内で文字が折り返されてますね。
2つの表の横幅は同じですが、高さは違います。
右側の表は「た。」だけの行があったりして無駄に高さを稼いじゃってますね。
なんかこれがいやだったので列幅を調整したりしてたんですが、エンジニアだったら合理的に幅を算出すべきじゃないかと思います。

数式で表すとどうなるだろうか

行$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}$

1行だけの表を例にして考える

これならほかの行との兼ね合いを考えなくていいので楽ですね。
表幅$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列目の列幅と行の高さの関係は下のグラフのようになります。

列1の幅が狭すぎる最初の方は$y=30/x$っぽいグラフで、逆に最後の方は$y=50/(20-x)$っぽくなってますね。
「し」型の関数と、左右反転した「し」型関数がぶつかってる感じです。
3次元(3列)になったら、これの真ん中に棒を刺して回したようなグラフになりそうです。最悪の場合、卵のパックみたいな局所解が散らばった図形になったりしそうです。

いかがでしたか

表を縦にコンパクトにするための列幅を探りました。なんか難しそうだったので前提を置きまくり、一番簡単なケースを総当たりで解いてみました。結果、そんなに複雑な解空間じゃないような気がしました。そりゃ一番簡単なケースを解いたんだからそうなるだろうという気もします。でも、「ほかの行との兼ね合い」という要素が加わっても、そんなに複雑にはならないんでしょうかわかりません。
ここまでやっといてなんですが、メタヒューリスティック手法で解くみたいなオチになると思います。問題について考えてみたけど上手く定式化できないからヒューリスティック手法で解くっていうのは全然合理的じゃない気がしますね。
教科書に載ってる練習問題は解けるのに応用的な文章題を出されると解けない優等生みたいな気分になりましたが、そもそもろくに教科書の問題を解けたことがありませんでした。精進します。