c++ - サブセット問題 -- 資料はありますか?

Question

はい、これは宿題/実験課題です。「バックトラッキング」を使用してサブセット和の問題を解決するためのアルゴリズムを考え出す/見つけることに興味があります (理解できます:P)。

誰でも役に立つリソースを持っていますか? 私は最後の 1 時間かそこらをグーグルで過ごしましたが、実際に使用できると思われるものを見つけることにあまり似ていませんでした。xD

ありがとうございます！

Answer 1

データをベクトルに入れます。

次に、ベクトル、インデックス、合計の 3 つの引数を持つルーチンを作成します。次の引数を指定してこのルーチンを呼び出します: ベクトル、0、0。

ルーチンは、次のタスクを実行する必要があります。

• ベクトルの終わり (index==size) に到達したかどうかを確認します。この場合、すぐに戻ることができます。
• 引数で自分自身を呼び出します: vector、index+1、sum+vector[index] (この場合、index の要素を sum に追加し、vector を続行します)
• 引数で自分自身を呼び出します: ベクトル、インデックス + 1、合計 (この場合、インデックスの要素を合計に追加しませんが、続行します)

このアルゴリズムでは、意図的に次の 2 つの部分を省略しました。

• まず、ある時点で合計を確認する必要があります。ゼロの場合、正しいサブセットが見つかりました
• 次に、使用した要素に関する知識も渡す必要があります。合計がゼロの場合は、サブセットを出力できます。これには STL::set の使用を検討してください。

または、関数の戻り値を使用して、正しいサブセットが既に見つかっているかどうかを判断できます。

アルゴリズムの複雑さは O(2^N) であるため、大きなセットでは非常に遅くなります。

楽しむ。