AtCoder ABC 054 D - Mixing Experiment (青色, 400 点)

なんだろ

問題へのリンク

問題概要

個の薬品があって、それぞれ成分 A, B を グラムずつ含んでいる (すべて整数値)。

これらのうちのいくつかを選んで混ぜ合わせることで、成分 A, B の比がちょうど : となるようにしたい。

そのようなことが可能となる薬品の組合せのうち、質量の総和の最小値を求めよ。

制約

• 
• 
• 

解法 1: ナップサック問題

とりあえず、全探索しようと思うと 通りになる。今回 がちょっと小さいとはいえ間に合わない。

でもこういう風に 通りという状況は、

• 部分和問題みたいな DP
• 半分全列挙

を疑いたくなる状況ではある。今回はどちらでもできる。部分和問題っぽくやってみる。

• dp[現在の個数][現在の重さ] := 価値の最大値だったり最小値だったり

という形が典型的だが、今回は成分 A, B の二つがあるので

• dp[現在の個数][現在の成分 A の重さ][現在の成分 B の重さ] := 価格の最小値 (実現できないなら INF)

としてみる。こういう DP テーブルを作っておいて、A の重さと B の重さの比がちょうど : になるところを調べれば OK。

#include <iostream>
#include <vector>
using namespace std;
void chmin(long long &a, long long b) { if (a > b) a = b; }
const long long INF = 1LL<<60;

int N;
long long ma, mb;
vector<long long> a, b, c;

long long dp[51][510][510];

int main() {
    cin >> N >> ma >> mb;
    a.resize(N); b.resize(N); c.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i] >> b[i] >> c[i];
    
    for (int i = 0; i < 51; ++i) for (int j = 0; j < 510; ++j) for (int k = 0; k < 510; ++k) dp[i][j][k] = INF;
    dp[0][0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int wa = 0; wa < 500; ++wa) {
            for (int wb = 0; wb < 500; ++wb) {
                if (dp[i][wa][wb] >= INF) continue;
                
                // 使わない
                chmin(dp[i+1][wa][wb], dp[i][wa][wb]);

                // 使う
                chmin(dp[i+1][wa+a[i]][wb+b[i]], dp[i][wa][wb] + c[i]);
            }
        }
    }
    long long res = INF;
    for (int wa = 1; wa < 500; ++wa) {
        for (int wb = 1; wb < 500; ++wb) {
            if (wa * mb != wb * ma) continue;
            chmin(res, dp[N][wa][wb]);
        }
    }
    if (res < INF) cout << res << endl;
    else cout << -1 << endl;
}

解法 2: 半分全列挙

ちょっとイメージしづらいけど、半分全列挙でもできる。