部分集合和と分割
選んだ部分集合で目標値を実現します
「部分集合和と分割」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
部分集合和の問題
数値と目標値が与えられたとき、いずれかの部分集合の合計をちょうど目標値にできますか。これは価値と重さが等しいナップサック問題です。
値ではなく真偽値DP
ここで追跡するのは最大値ではなく、到達可能かどうかです。dp[s]は、ある部分集合の合計がちょうどsになるときTrueとします。
dp = [False] * (target + 1)
dp[0] = True0は常に到達可能
空の部分集合の合計は0なので、dp[0]はTrueから始めます。それ以外の合計は、数値によって到達可能だと示されるまでFalseです。
遷移
各数値について、s - numがすでに到達可能なら、sも到達可能と印を付けます。1つの数値によって、多くの合計をTrueにできます。
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]再び逆向きにする
各数値は高々1回しか使えないため、内側のループは逆向きに実行します。これは0/1ナップサック問題と同じです。順方向では同じ数値を再利用してしまいます。
判定を読む
すべての数値を処理した後、dp[target]が答えになります。Trueなら有効な部分集合が存在し、Falseなら不可能です。
分割問題へ
分割問題では、配列を合計が等しい2つのグループに分けられるかを問います。これはそのまま部分集合和問題に帰着できます。
合計を半分にする
合計が奇数なら等しい2つのグループには分けられないため、すぐにnoと答えます。それ以外の場合、目標値は単純にtotal // 2です。
total = sum(nums)
if total % 2:
return False
target = total // 2部分集合和を再利用する
あとは、部分集合の合計がtotal // 2に到達するかを調べます。一方のグループが目標値に達すれば、残りの要素が自動的に一致するもう一方のグループになります。
計算量
計算量はnかけるtargetの擬多項式です。targetが小さいときは高速ですが、合計値が非常に大きいと遅くなります。
同じ仕組みを持つ問題群
部分和、分割、0/1ナップサックは、1つの仕組みを共有しています。取るか取らないかという形に気づけば、同じループを再利用できます。
クイックチェック
分割問題への帰着を確認します。
まとめ
ブール値DPと後ろ向きのループで部分和を解き、分割問題を合計値 // 2 に到達する問題へ帰着しました。同じ仕組みで、新たな問題も解けます。✅
よくある質問
「部分集合和と分割」レッスンは無料ですか？
はい。「部分集合和と分割」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「部分集合和と分割」で何を学びますか？
選んだ部分集合で目標値を実現します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「部分集合和と分割」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。