Maximum Winter-Contest 2011 C: Planning a Date

keyword

動的計画法　BruteForce　C++

問題概要

M(<10)人の議員がいて過半数以上の議員を買収しなければならない。各議員には時間の上限(<1000=S)と満足度の下限(<100=P)が与えられる。接待の方法はN(<10)とおりある。それぞれかかる時間、与える満足度、必要なコストが与えられる。総コストを最小化する問題。

解法

M人全ての議員について買収するのに必要な最小コストを前処理で計算しておけば後はBruteForceで解ける。各議員について買収する最小コストを求めるにはdp[使った時間][与えた満足度]としてDPで解ける。
計算量O(2^M + M*S*P*N)。

const int64 INF = 1LL<<50;

int N, M, GOAL;
int64 costs[20];
int64 dp[1009][109];
int S[20], P[20], C[20];
int curS[20], curP[20];

int64 preSolve(int x){
    int64 ret = INF;
    for(int i=0; i<=curS[x]+1; i++){
        for(int j=0; j<=curP[x]; j++){
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;
    for(int i=0; i<=curS[x]; i++)for(int j=0; j<=curP[x]; j++)if(dp[i][j]!=INF){
        for(int k=0; k<N; k++){
            int ns = i + S[k], np = j + P[k];
            ns = min(curS[x]+1, ns);
            np = min(curP[x], np);
            dp[ns][np] = min(dp[ns][np], dp[i][j] + C[k]);
        }
    }
    for(int i=0; i<=curS[x]; i++){
        ret = min(ret, dp[i][curP[x]]);
    }
    return ret;
}

int64 solve(){
    GOAL = M/2 + 1;
    for(int i=0; i<M; i++){
        costs[i] = preSolve(i);
    }
    int64 ret = INF;
    for(int bit=0; bit<1<<M; bit++)if(__builtin_popcount(bit)>=GOAL){
        int64 tmp = 0;
        for(int i=0; i<M; i++)if((bit>>i)&1) tmp += costs[i];
        ret = min(ret, tmp);
    }
    return ret==INF?-1:ret;
}

int main(){
    while(scanf("%d%d",&N,&M)){
        if(!N && !M) break;
        for(int i=0; i<N; i++){
            scanf("%d%d%d",S+i,P+i,C+i);
        }
        for(int i=0; i<M; i++){
            scanf("%d%d",curS+i,curP+i);
        }
        cout << solve() << endl;
    }
    return 0;
}