1

これは私の以前の質問(古いトップ コーダーのなぞなぞについて)のフォロー アップです。

数字の文字列が与えられた場合、その文字列が目的の数値に等しくなるために必要な加算の最小数を見つけます。各追加は、数字の文字列のどこかにプラス記号を挿入することと同じです。すべてのプラス記号が挿入されたら、通常どおり合計を評価します。

たとえば、「303」と目標の合計が 6 であるとします。最適な戦略は「3+03」です。

私は（それを証明していませんが）問題はNP完全だと思います。どう思いますか？よく知られている NP 完全問題をこの問題にどのように還元しますか?

4

3 に答える 3

1

番号の後に期待される結果を追加すると、これがhttp://en.wikipedia.org/wiki/Partition_problemであることが明らかです。

于 2011-12-08T11:28:22.613 に答える
1

ベースをパラメーターにすると、サブセットの合計からの削減があります。x 1 , …, x n , s > 0 をサブセット合計のインスタンスとし、S = x 1 + … + x nとします。ベース S + 1 で、トップ コーダー入力を次のようにします。

x 1 0 x 2 0 … x n 0

(S - s) (S + 1) + s に合計します。

もちろん、はるかに興味深いのは、ベース10ケースの硬度です。

于 2011-12-08T12:43:07.570 に答える