金貨の価値は銀貨の価値より十分高く、銀貨の価値は銅貨の価値より十分高いので、

• まず、金貨の所持数がより多い方がより良い状態であり、
• それが同数の場合は、銀貨の所持数がより多い方がより良い状態であり、
• さらにそれも同数の場合は、銅貨の所持数がより多い方が良い状態

であると考えます。

\(i = 1, 2, \ldots, N\) の順番に \(i\) 番目の袋を買うか買わないかを決定していくときの、最終的な（金貨、銀貨、銅貨）の所持枚数としてあり得る最良の状態を動的計画法（DP）で求めます。 DP テーブルとして、\(i = 0, 1, 2, \ldots, N\) と \(j = 0, 1, 2, \ldots, X\) について、

\(\mathrm{dp}[i][j] = \)（ \(i\) 番目の袋まで買うか買わないかを決定しており、銅貨の所持残数が \(j\) 枚であるときの所持している（金貨, 銀貨）の枚数の組としてあり得る最良の組）

とおきます。（金貨の所持数がより多い方がより良い組であり、 それが同数の場合は銀貨の所持数がより多い方がより良い組であると考えます。）

DP の初期状態を考えます。 はじめは、金貨 \(0\) 枚、銀貨 \(10^9\) 枚、銅貨 \(X\) 枚を所持しているので、\(\mathrm{dp}[0][X] = (0, 10^9)\) です。 \(j = 0, 1, 2, \ldots, X-1\) については便宜上 \(\mathrm{dp}[0][j] = (-\infty, -\infty)\) とします。

次に DP の遷移を考えます。 現在 \(i\) 番目までの袋の決定を終えており、所持する銅貨の枚数が \(j\) 枚であるとします。

• \(i\) 番目の袋を買った場合：\(i-1\) 番目までの袋の決定を終えた時点では、銅貨を \(j+A_i\) 枚持っていたことになり、所持する（金貨、銀貨）の枚数も \((+C_i, -B_i)\) されています。
• \(i\) 番目の袋を買わなかった場合：\(i-1\) 番目までの袋の決定を終えた時点の銅貨の所持数も \(j\) 枚であり、（金貨、銀貨）の所持数も変わっていません。

上記の \(2\) つのパターンを考慮すると、遷移の漸化式

\[\mathrm{dp}[i][j] = \max\lbrace \mathrm{dp}[i-1][j], \mathrm{dp}[i-1][j+A_i] + (C_i, -B_i)\rbrace\]

が得られます。

上記の初期化と遷移にしたがって DP テーブルを計算し、 最終的な（金貨、銀貨、銅貨）の枚数の組としてあり得るものの集合 \(\lbrace (P, Q, j) : (P, Q) = \mathrm{dp}[N][j], 0 \leq j \leq X \rbrace\) のうちで最良のものを出力すれば本問題を \(\mathrm{O}(NX)\) 時間で解くことができます。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
#include <tuple>
using namespace std;

int n, x;
int a[3005], b[3005], c[3005];
tuple<int, int> dp[3005][3005];
 
int main(void)
{
  cin >> n >> x;
  for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
  
  for(int i = 0; i <= n; i++) for(int j = 0; j <= x; j++) dp[i][j] = {-1e9, -1e9};
  dp[0][x] = {0, 1e9};
  
  for(int i = 1; i <= n; i++){
    for(int j = 0; j <= x; j++){
      dp[i][j] = dp[i-1][j];
      if(j+b[i] <= x){
        dp[i][j] = max(dp[i][j], {get<0>(dp[i-1][j+b[i]])+c[i], get<1>(dp[i-1][j+b[i]])-a[i]});
      }
    }
  }
  tuple<int, int, int> ans = {0, 0, 0};
  for(int j = 0; j <= x; j++) ans = max(ans, {get<0>(dp[n][j]), get<1>(dp[n][j]), j});
  cout << get<0>(ans) << " " << get<1>(ans) << " " << get<2>(ans) << endl;
  
  return 0;
}