整数分割2

続き、

  • The partition after [1, 1, 3, 3] is [1, 2, 2, 3], for after subtracting 1 from 3, we should pack the three units that result in parcels of size 2.

そのまま訳せば、分割アルゴリズの過程において[1,1,3,3]の次の分割は[1,2,2,3]である。[1,1,3,3]のうち1を除いた最小の数は3であるからm = 3となり、m - 1 で2。とここまでは良い。次が、”we should pack the three units that result in parcels of size 2″なんだけど、「残り3つの要素を最大サイズ2にまとめなければならならない」で良いのだろうか?

The partition after [1, 1, 1, 1, 1, 1, 5] is [3, 4, 4], for after subtracting 1 from 5, we should pack the seven units that result in parcels with maximum size 4, which gives three units and one parcel of size 4, which in turn gives one parcel of size 3 and one of size 4. The partition after [3, 3, 5] is [1, 2, 3, 5]. The partition after [1, 3, 3, 4] is [2, 2, 3, 4].

[1,1,1,1,1,1,5]の次は[3,4,4]。ここでも1以外の最小値 m = 5とし、ここまでは前段の例と同じ。でも次の一文が”we should pack the seven units that result in parcels with maximum size 4,”とある。前段では”we should pack the three units”、が今度は”we should pack the seven units”とあって、前段の例に合わせるのであれば”six units”じゃないかな?あるいは後段合わせるなら最初の例は”four units”になるか…

ヒントは続く一文?”which gives three units and one parcel of size 4, which in turn gives one parcel of size 3 and one of size 4.” 4つある要素”1″の3つとm - 1 の”1″を合わせて4と、残りの3つの”1″を合計して3ってこと?