>>59
> 効率のよいアルゴリズムを教えていただけないでしょうか。 
コストが超増加性をもつなら話は別かもしれないけど
準NPにこの発言は鬼門

というわけで総当りが妥当