[Python] ABC015 D 全探索 0点

問題

D – 高橋くんの苦悩

回答

TLE で 0点ですが、まずは再帰的に行う全探索を考えます。

p32 です。

W = int(input())
N, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

def dfs(used_w, used_n, now):
    """
    used_w 今まで選んだ合計幅
    used_n 今まで選んだ合計数
    now 今調べる番号
    """
    # 終了条件
    if now == N:
        return 0
    if used_w >= W or used_n >= K:
        return dfs(used_w, used_n, now+1)

    # 終了条件を満たさない場合
    a = AB[now][0] # 幅
    b = AB[now][1] # 重要度
    # 更新できる場合  
    if used_w + a <= W and used_n + 1 <= K:
        val_used = dfs(used_w + a, used_n + 1, now+1) + b
        val_not_used = dfs(used_w, used_n, now+1)
        return max(val_used, val_not_used)    
    # 更新できない場合
    return dfs(used_w, used_n, now+1)

print(dfs(0, 0, 0))