\(T\subset \lbrace 1,2,\ldots,N\rbrace\) と \(0\le x\le X\) に対し \(d[T][x]\) を「現在すでに \(T\) に含まれる問題を正解しており、所持金が残り \(x\) 円である場合の得点の期待値の最大値」とする動的計画法を考えます。

\(d[T][x]\) の満たす漸化式について考えます。

まず、問題 \(i\) に提出した場合（\(i \notin T,\ x\geq C_i\)）\(P_i\) % の確率で正解し \(100-P_i\) %の確率で不正解となるので、この場合の得点の期待値の最大値は \(\displaystyle \frac{P_i}{100}\left(S_i+d[T\cup\lbrace i\rbrace][x - C_i] \right) + \frac{100-P_i}{100}d[T][x - C_i] \) です。したがって、まだ正解していない問題全てに対してこの期待値を計算し、その最大値を \(d[T][x]\) とすれば良いです。

この動的計画法を行なった際の \(\displaystyle d[\varnothing][X]\) が答えとなります。計算量は \(O(NX2^N)\) 時間です。

実装例(Python3)

N, X = map(int, input().split())
S = [0] * N
C = [0] * N
P = [0] * N
for i in range(N):
    S[i], C[i], P[i] = map(int, input().split())
    P[i] /= 100
d = [[0.0 for _ in range(X + 1)] for _ in range(1 << N)]
for x in range(X + 1):
    for s in range(1 << N):
        for i in range(N):
            xx = x - C[i]
            ss = s | (1 << i)
            if xx < 0 or s == ss:
                continue
            val = P[i] * (d[ss][xx] + S[i]) + (1 - P[i]) * d[s][xx]
            d[s][x] = max(d[s][x], val)
print(d[0][X])