なんだろ
問題概要
個の薬品があって、それぞれ成分 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: 半分全列挙
ちょっとイメージしづらいけど、半分全列挙でもできる。