U = {√1, √2, …, √50}を2つのグループに分け、グループ毎の和を求める。和の差がなるべく小さくなるようなグループ分けを、制限時間10秒で見つけよ。
10秒という制限時間で、2の49乗個の候補の中から最良のものを見つけ出すのは、1977年当時のコンピュータでは難しかったはずです。そこでKnuthは、以下のような工夫をしました。
- まず小数部分を近づけることを目指し、その後で整数部分を近づける。（この問題では結果オーライ。√40までの場合はうまくいかない。）
- I = {√1, √4, √9, √16, √25, √36, √49}は、和の整数部分にしか関与しないから後で考えることにする。
- Uを2つのグループAとBに分け、Aの部分集合とBの部分集合の合計の小数部分を、全体の合計の半分の小数部分に近づける。
- Aの部分集合の小数部分をすべて記録しておき、Bの部分集合に対して、上の条件に会うようなAの部分集合がすぐに見つかるようにする。
- 部分集合の生成にはグレイコードを使う。
- X = {√2, √8, √18, √32, √50}の組み合わせでできる和は16通りしかないことを利用する。同様に、Y = {√3, √12, √27, √48}の組み合わせでできる和は11通りしかないことも利用する。
- 集合をA = X ∪ Y ∪ {√5, √6, √7, √10, √11, √13, √14, √15}、B = U – I – Aとする。
今日のコンピュータは当時と比べればはるかに強力なので、これらの工夫のうちの1から4を採用するだけで、あとは富豪的なプログラムでも最良解を見つけるのに5秒とかかりません（コード）。本稿執筆時点のideone.comで約2.5秒(double)あるいは約2.8秒(long double)、私のデスクトップ（Core i7 950 3.07Ghz）のVisual C++で約1.3秒でした（いずれもシングルスレッド）。
Aの部分集合の記録には、C++11で導入されたunordered_multimapを使いました。キーAのサブセット和の小数部分8桁を、値はサブセットを表現する整数とサブセット和のpairです（この実装では、mapよりunordered_mapのほうがかなり速いです）。sizeAを20にしたり、keyを小数点以下8桁にすると速いのは、動かしてみてわかったことです。