AtCoder Beginner Contest 054 D - Mixing Experiment

問題

atcoder.jp

問題概要

薬品がN個あり、i個目の薬品はタイプAの薬品をa[i-1]グラム、タイプBの薬品をb[i-1]グラム含み、価格はc[i-1]である。
これらの薬品のうちからいくつか選んで混合し、タイプAとタイプBの薬品の混合比がMa:Mbとなるようにしたときの最小予算を求めよ。

解法

ナップサックdpに似ている。

dp[i][j][k] : i番目(1-index)の薬品まで見てタイプAがjグラム、タイプBがkグラム混合されるようにしたときの最小予算。
0≦i≦N、0≦j≦Σa[i]、0≦k≦Σb[i]

今回は「～以内」ではなく「ちょうど～」なのでそのような組み合わせが存在しないことがある。この時のことも考えなくてはいけないため場合分けが多くなる。

最小値を求めたいのでdpはINFで初期化する。

dp[i][j][k]=INFの時はi番目まで見てタイプAがjグラム、タイプBがkグラム混合されるように選ぶ方法はないということである。

i番目を混合するか混合しないかの2通りある。

i番目を混合しないとき
dp[i][j][k]=dp[i-1][j][k]

i番目を混合するとき
dp[i][j][k]=dp[i-1][j-a[i-1]][k-b[i-1]]+c[i-1]

これらのうちの小さいほうである
ただしj-a[i-1]<0またはk-b[i-1]<0の時は配列外参照になるため
dp[i][j][k]=dp[i-1][j][k]となる。
また、dp[i-1][j][k]=INFかつdp[i-1][j-a[i-1]][k-b[i-1]]=INFの時は
dp[i][j][k]も作れないのでINFとなる。

i=0の時は
j=0かつk=0の時はdp[i][j][k]=0となり、
それ以外の時は作れないのでdp[i][j][k]=INFとなる。

答えはi=Nでj:k=Ma:Mbとなるdp[i][j][k]のうちの最小値である。

ソースコード

signed main() {
	int N, Ma, Mb;
	cin >> N >> Ma >> Mb;
	vector<int>a(N);
	vector<int>b(N);
	vector<int>c(N);
	rep(i, N) {
		cin >> a[i] >> b[i] >> c[i];
	}
	int Sa = 0;
	int Sb = 0;
	rep(i, N) {
		Sa += a[i];
		Sb += b[i];
	}
	Sa++;
	Sb++;
	vector<vector<vector<int>>>dp(N + 1, vector<vector<int>>(Sa, vector<int>(Sb,INF)));
	rep(i, N + 1) {
		rep(j, Sa) {
			rep(k, Sb) {
				if (i == 0) {
					if (j == 0 && k == 0) {
						dp[i][j][k] = 0;
					}
				}
				else {
					if (j - a[i - 1] < 0 || k - b[i - 1] < 0) {
						dp[i][j][k] = dp[i - 1][j][k];
					}
					else {
						if (dp[i - 1][j][k] == INF && dp[i - 1][j - a[i - 1]][k - b[i - 1]] == INF) {
							dp[i][j][k] = INF;
						}
						else {
							dp[i][j][k] = min(dp[i - 1][j][k], dp[i - 1][j - a[i - 1]][k - b[i - 1]] + c[i - 1]);
						}
					}
				}
			}
		}
	}
	int ans = INF;
	rep(i, N + 1) {
		rep(j, Sa) {
			rep(k, Sb) {
				if (i == N && j * Mb == k * Ma &&j!=0&&k!=0) {
					ans = min(ans, dp[i][j][k]);
				}
			}
		}
	}
	if (ans == INF) {
		cout << -1 << enld;
	}
	else {
		cout << ans << endl;
	}
}