[boj](s 2)1182部分数列の和

1577 ワード
boj テキストリンク
瓇DFS瓇backトラッキング

質問する


リンク

に答える


1.質問へのアクセス


数列のすべてのサブセットで、要素の和がSの場合、数を要求します.
では、すべての部分集合の要素の和を求めるべきではないでしょうか.
大きさNの数列の部分集合の数は2^N個であり,Nの最値は20であるため,合計1048576個である.多すぎます...
もしそうなら、枝を切ることで状況の数を減らすべきです.->ついせき

2.トラブルシューティングロジック（解法）


遡及(枝切り)の基本論理
ノードの潜在力を確認すると、
希望がなければ除外する.枝を切る
ノードの親ノードを返すと、他の子ノードが検索されます.→解法時間短縮
  • の部分集合からすべての集合を抽出できないため、DFSを使用して説明できることは知られているが、逆追跡の実装アルゴリズムDFSを実行することはできない.
    すなわち,再帰的に修枝条件に遭遇した場合,直ちに親ノードに戻ることができる.
  • の部分集合は、各要素が含まれているかどうかの問題です.
    したがって、枝切りの「枝」は、要素を順次追加するかどうかに分けることができます.
  • 修枝の条件は、要素の順序が数列の大きさを超えてはならないことです.

    • ぎじふごう

    int cnt = 0

void DFS(int sum, int idx){ // sum : 현재까지 더해진 총 값, idx : 더할 원소의 인덱스
	if(sum + arr[idx] == S) cnt ++
    if(idx == N) return;
    
    DFS(sum, idx+1) // 더하지 않고 다음 원소로 이동
    DFS(sum + arr[idx], idx+1) // 더하고 다음 원소로 이동
}

main(){
	cin >> N >> S
    for(i : 0 ~ N-1){
    	cin >> arr[i]
    }
    
    DFS(0,0) // 0번째 원소부터 더해감
    
    cout << cnt
}

    3.時間複雑度分析


    O(2N)O(2^N)O(2N)

    4.問題の重要な部分


  • サブセットとは、各要素が含まれているかどうかの問題です.
    要素を順番に移動して、加算しないに分けるだけでいいです.

  • 枝を直す条件を知るのは難しい.
    最初はNの値によって枝分かれするべきだと思っていましたが、数列の中には負数も正数も存在するので、Nの値によって枝分かれすることはできません.
    では残り(?)条件に反するのは、要素が順番に追加されているため、数列のインデックスから離れることはできません.
    • パーティーが終わったら
    ムービーシードAPIの作成とスクロール