問題

https://beta.atcoder.jp/contests/abc054/tasks/abc054_d

N 個の薬品があり、それぞれ a_i, b_i, c_i で与えられる。各 i は1回まで選択できる。Σ a_i : Σ b_i = M_a : M_b となるようにいくつか薬品を選択するときの最小の Σ c_i を求めよ。

制約

1 <= N <= 40
1 <= a_i, b_i <= 10
1 <= c_i <= 100
1 <= M_a, M_b <= 10
1 <= gcd(M_a, M_b) = 1
入力値は整数

考え方

通常のナップザックDPと同じである。i 個選択してタイプAの合計 A, タイプBの合計 B である状態を f (i, A, B) とし、そのときの状態の遷移を考えると、

(1)薬品 i を選択したとき
f (i, A, B) は f (i+1, A+a_i, B+b_i) に遷移する

(2)薬品 i を選択しないとき
f (i, A, B) は f (i+1, A, B) に遷移する

ことがわかる。後は薬品を N 個入れたときのタイプAとタイプBの値をチェックし、Ma : Mbの比の条件を満たしているときの金額の最小値を選択すれば良い。

       int n, Ma, Mb;
        int[] a, b, c;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            n = in.nextInt();
            Ma = in.nextInt();
            Mb = in.nextInt();

            a = new int[n]; b = new int[n]; c = new int[n];

            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
                b[i] = in.nextInt();
                c[i] = in.nextInt();
            }
            int maxA = Arrays.stream(a).sum();
            int maxB = Arrays.stream(b).sum();

            int[][][] dp = new int[n+1][maxA+1][maxB+1];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j <= maxA; j++) {
                    for (int k = 0; k <= maxB; k++) {
                        dp[i][j][k] = INF;
                    }
                }
            }

            dp[0][0][0] = 0;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j <= maxA; j++) {
                    for (int k = 0; k <= maxB; k++) {
                        if (j >= a[i] && k >= b[i]) {
                            dp[i+1][j][k] = Math.min(dp[i][j-a[i]][k-b[i]]+c[i], dp[i][j][k]);
                        } else {
                            dp[i+1][j][k] = dp[i][j][k];
                        }
                    }
                }
            }

            int ans = INF;
            for (int sa = 1; sa <= maxA; sa++) {
                for (int sb = 1; sb <= maxB; sb++) {
                    if (sa * Mb == sb * Ma) {
                        ans = Math.min(ans, dp[n][sa][sb]);
                    }
                }
            }

            out.println(ans == INF ? -1 : ans);
        }