全ての商品の価格が \(100\) の倍数である場合を考えてみましょう。

価格が \(P\) 、効用が \(U\) の商品を買うと、\(\frac15P\) の商品券がもらえるので、買い物のスコアは \(U - \frac45P\) 増加します。
したがって、\(U - \frac45P\) が正の商品を全て購入すれば良いです。

商品の価格が \(100\) の倍数でない場合、商品券にならない端数の部分が生まれます。
よって、以下のような問題に言い換えることができます。

• 価格が \(P\) 、効用が \(U\) の商品を買うと、買い物のスコアが \(U - P + 20 \times \lfloor\frac P{100}\rfloor\) 増加し、端数が \(P \bmod 100\) 貯まる。
• 端数が \(100\) 貯まると、買い物のスコアが \(20\) 増加する。

この問題は、以下のような動的計画法で解くことができます。

\(dp[i][j] = {}\)( \(i\) 個目までの商品のうちいくつかを買って、端数が \(j\) であるときの買い物のスコアの最大値 )

漸化式は以下のようになります。

\[ \begin{aligned} dp[i][j] = \max(&dp[i-1][j],\\ &dp[i-1][j-(P\bmod 100)] + (U - P + 20 \times \lfloor\tfrac P{100}\rfloor),\\ &dp[i-1][j-(P\bmod 100) + 100] + (U - P + 20 \times \lfloor\tfrac P{100}\rfloor) + 20)\\ \end{aligned} \]

回答例 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3fffffff;
void chmax(int& a, int b){ if(a < b) a = b; }

int main(){
    int N;
    cin >> N;
    vector dp(100, -INF);
    dp[0] = 0;
    while(N--){
        int P, U;
        cin >> P >> U;
        U += P / 100 * 20 - P;
        P %= 100;
        const auto dp2 = dp;
        for(int i = P; i < 100; i++) chmax(dp[i], dp2[i - P] + U);
        for(int i = 0; i < P; i++) chmax(dp[i], dp2[i - P + 100] + U + 20);
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
}

回答例 (Python)

N = int(input())
dp = [-1 << 60] * 100
dp[0] = 0
for _ in range(N):
    P, U = map(int, input().split())
    U += P // 100 * 20 - P
    P %= 100
    dp2 = dp[:]
    for i in range(P, 100):
        if dp[i] < dp2[i - P] + U:
            dp[i] = dp2[i - P] + U
    for i in range(P):
        if dp[i] < dp2[i - P + 100] + U + 20:
            dp[i] = dp2[i - P + 100] + U + 20
print(max(dp))