深さ判別法

yamagenii 16views 更新:2016年8月29日

n個の数列a0,…,anがあたえられたとき、その数列を組み合わせて得られた和がkであるかどうか判別するアルゴリズムを深さ判別法で解く

深さ判別法は全探索のアルゴリズムで、 オーダーはO(2^n)であるので、n=20程度であれば、解くことが出来る。それ以上になる場合は効率的なアルゴリズムを考えなければならない。

#include <iostream>
#include <vector>
using namespace std;

int n,k;
vector<int> a;

bool dps(int i, int sum){
    if(sum == k) return true;
    else if(i == a.size()) return false;
    if(dps(i+1,sum + a[i])) return true;
    if(dps(i+1, sum)) return true;
    return false;
}

int main(){
    cin >> n;
    for (int i = 0;i < n; i++){
        int m;
        cin >> m;
        a.push_back(m);
    }
    cin >> k;
    bool ans = dps(0,0);
    cout << ans <<endl;
    return 0;
}
input (標準入力)
4
1 2 4 7
13

output (標準出力)
1

ログイン / 新規登録してコメントする

このソースコードをストックして後で利用したり、作業に利用したソースコードをまとめることができます。

こちらもお役に立つかもしれません