この解説は、DP の到達状態を後ろから復元し，最適解に含まれるかどうかを判定する解法です。

公式解説と同様に、まずは \(M\) 円以下となるように選んだときの価値の合計の最大値を求めます。
以下の DP 部分については公式解説とほぼ同じですが、値段が「\(j\) 円以下」ではなく「ちょうど \(j\) 円」である点に注意してください。

\(\text{dp}[i][j]\ (0 \le i \le N,\ 0 \le j \le M)\) を

• 「\(1\) 番目から \(i\) 番目までの商品からいくつか（\(0\) 個でもよい）選び，値段の合計がちょうど \(j\) 円となるようにしたときの，価値の合計の最大値」

として定義します。

初期値は \(\text{dp}[0][0] = 0\)、遷移は

• \(j < P_i\) のとき：\(\text{dp}[i][j] = \text{dp}[i-1][j]\)
• \(j \ge P_i\) のとき： \(\text{dp}[i][j] = \max\bigl(\text{dp}[i-1][j],\ \text{dp}[i-1][j-P_i] + V_i \bigr)\)

となります。
最終的に、\(\max_{0 \le j \le M} \text{dp}[N][j]\) が価値の最大値となり，これを \(X\) とします。

価値 \(X\) を達成する遷移の復元

ここで，配列 \(\text{reachable}[i][j]\) を

• 「\(1\) 番目から \(i\) 番目までの商品からいくつか選んで値段の合計を \(j\) 円としたとき， そこから先を適切に選ぶことで最終的な価値 \(X\) を達成できるかどうか」

を表すものとします。 あわせて，次の 2 つの配列も用意しておきます。

• \(\text{use}[i]\)：価値 \(X\) を達成するような最適解の中に，「商品 \(i\) を選ぶ」遷移が少なくとも 1 回は存在するかどうか
• \(\text{skip}[i]\)：価値 \(X\) を達成するような最適解の中に，「商品 \(i\) を選ばない」遷移が少なくとも 1 回は存在するかどうか

まず，\(\text{dp}[N][j] = X\) となるすべての \(j\) について \(\text{reachable}[N][j] = \text{true}\) とします。

次に，\(i = N, \dots, 1\) の順に DP を逆向きに辿ります。もし\(\text{reachable}[i][j] = \text{true}\) であれば，状態 \((i, j)\) から価値 \(X\) を達成できるので，\((i-1, j') \to (i, j)\) の遷移が存在するかを調べます。

\(\text{dp}[i-1][j] = \text{dp}[i][j]\) であれば \((i-1, j) \to (i, j)\) の「商品 \(i\) を選ばない」遷移が存在するため，

• \(\text{reachable}[i-1][j] = \text{true}\)
• \(\text{skip}[i] = \text{true}\)

とします。

\(j \ge P_i\) かつ \(\text{dp}[i-1][j - P_i] + V_i = \text{dp}[i][j]\) であれば，\((i-1, j-P_i) \to (i, j)\) の「商品 \(i\) を選ぶ」遷移が存在するため，

• \(\text{reachable}[i-1][j-P_i] = \text{true}\)
• \(\text{use}[i] = \text{true}\)

とします。

以上により，各商品 \(i\) について次のように分類できます。

• \(\text{use}[i] = \text{true}\) かつ \(\text{skip}[i] = \text{false}\)
  → 価値 \(X\) を達成する最適解では 必ず選ぶ（分類 A）

• \(\text{use}[i] = \text{true}\) かつ \(\text{skip}[i] = \text{true}\)
  → 選ぶ解と選ばない解の 両方が存在する（分類 B）

• \(\text{use}[i] = \text{false}\) かつ \(\text{skip}[i] = \text{true}\)
  → 価値 \(X\) を達成する最適解では 選ばない（分類 C）

時間計算量は前半のDP、後半の復元共に\({O(NM)}\)となります

C++ による実装例:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int N, M;
	cin >> N >> M;
	vector<ll> p(N), v(N);
	for (int i=0; i<N; ++i) cin >> p[i] >> v[i];

	//DP本体
	vector dp(N+1, vector(M+1, -(1LL << 60)));
	dp[0][0]=0;
	for (int i=0; i<N; ++i) {
		for (int j=0; j<=M; ++j) {
			if (j < p[i]) dp[i+1][j] = dp[i][j];
			if (j >= p[i]) dp[i+1][j] = max(dp[i][j], dp[i][j-p[i]] + v[i]);
		}
	}

	const ll X = *max_element(dp[N].begin(), dp[N].end()); //最大値
	vector use(N, false); //商品iを選ぶ遷移がある
	vector skip(N, false);  //商品iを選ばない遷移がある
	vector reachable(N+1, vector(M+1, false));

	for (int j=0; j<=M; ++j) {
		if (dp[N][j] == X) reachable[N][j] = true;
	}

	for (int i=N-1; i>=0; --i) {
		for (int j=0; j<=M; ++j) {
			if (!reachable[i+1][j]) continue;

			//商品iを選ばない遷移
			if (dp[i][j] == dp[i+1][j]) {
				reachable[i][j] = true;
				skip[i] = true;
			}
			//商品iを選ぶ遷移
			if (j >= p[i] && dp[i][j-p[i]]+v[i] == dp[i+1][j]) {
				reachable[i][j-p[i]] = true;
				use[i] = true;
			}
		}
	}

	string ans = "";
	for (int i=0; i<N; ++i) {
		if (use[i] && !skip[i]) ans += "A";
		if (use[i] && skip[i]) ans += "B";
		if (!use[i] && skip[i]) ans += "C";
	}
	cout << ans << "\n";
}