最適な食べ方があるとすると, その食べる順序は \(A_i\) が小さい順に並べても可能である. よって \(A_i\) の昇順にソートしておく.

\(i\) 番目の食べ物まで見たときに \(j\) 分経過したときの最大の幸福度を \(H(i, j)\) とすると,

\[H(i, j) = \max(H(i-1, j), H(i-1, j-A_i) + B_i)\]

となる. これを DP で計算する. ただし, \(j-A_i >= T\) となる部分は計算しない.