ABC 015 D 高橋くんの苦悩 - いろんなことで四苦Hack（仮）

自分がやりたいことは、自分が実行しない限り一生達成されることはない。えぬわいです。

続きです。

問題のURLです。

DPな日々。ちょっと慣れてきました。

ナップザック問題に、個数の制限がかかったような問題です。

限界重さと、選ぶことができる最大の個数が決まっており、その中から最大の価値を捻出するという概要。

W = int(input())
N, K = map(int, input().split())
a, b = ([], [])

for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa); b.append(bb)

"""
def rec(i, j, k):
    # i 番目以降から j 個選んだ時の選んだ時の最大の価値を返す
    if i >= N:
        return 0
    if j >= K:
        return 0
    ans = 0
    # 入れる
    if k >= a[i]:
        ans = rec(i+1, j+1, k-a[i])+b[i]
    ans = max(rec(i+1, j, k), ans)
    return ans

print(rec(0, 0, W))
"""

dp = [[[0 for z in range(W+1)] for y in range(K+1)] for x in range(N+1)]

# N が初期値が入っている段になっているので、N-1から。
# また、0 にも入れたいので、0 を含む
# O(NKW) になってTLE
for i in range(N-1, -1, -1):
    for j in range(K-1, -1, -1):
        # W に入れたいので
        for k in range(W+1):
            if k >= a[i]:
                dp[i][j][k] = max(dp[i+1][j+1][k-a[i]]+b[i], dp[i+1][j][k])
            else:
                dp[i][j][k] = dp[i+1][j][k]

print(dp[0][0][W])

前半部分に、再帰関数が書いてあります。後半で、DP化。

pythonで書くと、TLEで死ねます。これは、TLEです。

cpp で書き直します。

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[50+1][50+1][10000+1], a[50], b[50];

int W, N, K;

int main() {
    scanf("%d", &W);
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &a[i], &b[i]);
    }

    for (int i = N-1; i >= 0; i--) {
        for (int j = K-1; j >= 0; j--) {
            for (int k = 0; k <= W; k++) {
                if (k >= a[i]) {
                    dp[i][j][k] = max(dp[i+1][j+1][k-a[i]]+b[i], dp[i+1][j][k]);
                } else {
                    dp[i][j][k] = dp[i+1][j][k];
                }
            }
        }
    }
    printf("%d\n", dp[0][0][W]);
    return 0;
}

python でTLEったときは、DPがおかしいのかなと思ったけど、c++で試したら通ったんで、まぁいいのかなという感じです。

パッと見で、問題がナップザックっぽいなって思えたのは、成長かも。なにくそにゃー、まだ成長するかもらー。

この調子でやり続けたいと思います。