3628:Bookshelf 2

PKU

keyword

BruteForce　C

概要

長さN(<20)の数列と整数Bが与えられる。全ての和がB以上になる部分列の中で最小のもとを求める問題。
Nが小さいので全探索する。パターンが2^N、部分和の計算がNなので全体の計算量はO(2^N * N)。半分全列挙を用いるとO(2^(N/2) * N)に落とせる(2^(N/2) * log(2^(N/2))。

int hs[22];
int N, B;

int solve(){
    int i, cnt, mask, ans = 1<<30;
    for(mask=0;mask<1<<N;mask++){
        cnt = 0;
        for(i=0;i<N;i++)if((mask>>i)&1)
            cnt += hs[i];
        if(cnt >= B && ans > cnt - B)
            ans = cnt - B;
    }
    return ans;
}