ガーディアン(英国の新聞)の今日の版では、クリス・マスランカによる43ページの「ピルジックパズル」セクションで、次のパズルが与えられました。
東方の三博士は...クリスマスの買い物をするためにハロッズに行きました。キャスパーはゴールドを購入し、メルヒオールはフランキンセンスを購入し、バルタザールはデイリーミルラのコピーを購入しました。レジ係は、これらのそれぞれのコストのユーロ数を利用し、3つの数値を加算することを意図していましたが、代わりにそれらを乗算しました。...驚異的なのは、結果がまったく同じであるということでした:€65.52。3つの合計は何でしたか[彼は3つの数字を意味していると思います]?
私の解釈は次のとおりです。a+b+ c = abc = 65.52(正確に)となるようなa、b、cを見つけます。ここで、 a 、 b 、 cは小数点以下2桁以下の正の小数です。したがって、 a、b、およびcも65.52(約)未満である必要があります。
したがって、私のアプローチは次のとおりです。a、b、およびcのすべての候補セットを見つけます。ここで、a + b + c = 6552であり、 a、b、およびcは{1 ... 6550}からの整数です(概念的には、すべてのオペランドを乗算しました便宜上100ずつ)。次に、すべての候補セットについて、すべてのオペランドを100で除算し、それらを乗算することによって(任意精度の演算を使用して)、他の条件を満たすのは簡単です。
これは、私が見ているように、サブセット和問題のインスタンスです。そこで、ダーティ(指数時間)アルゴリズムを実装しました。これにより、a = 0.52、b = 2、c=63という1つの明確な解決策が見つかりました。
サブセット和問題にはもっと良いアルゴリズムがありますが、これは平均的なGuardianリーダーには少し手が届かないものになっていると思いませんか?
40ページに答えがリストされています:
これは試行錯誤で簡単です。デイリーミルラの52pを推測します。しかし、0.52を掛けると、およそ半分になるので、1つの合計が約2になる必要があります。したがって、2 X 63X0.52を試してください。Etvoilà。この答えはユニークですか?
まあ、私たちは答えがユニークであることを知っています(2、63、0.52の他の順列を無視して)。
私が知りたいのは、どうすればこれを「簡単」にできるのかということです。パズルを部分和問題のインスタンスとして特徴づけるのは正しいですか?ソリューションを簡素化するために利用できるパズルのいくつかの特徴を見落としていませんか?誰かが同様の「試行錯誤」のアプローチを採用することができましたか?もしそうなら、彼らは私をそれを通して連れて行くことができますか?クリス・マスランカは、NP完全問題に単純に臆することはありませんか?