[SWEA / PYTHON] 3282. 0/1 Knapsack

import os
import sys


current_file = os.path.basename(__file__)[:-3]
sys.stdin = open(f"input/{current_file}_input.txt", "r")


result = []

T = int(input())


def knapsack(W, wt, val, n):
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0

            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])

            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][W]


for case in range(1, T + 1):
    N, K = map(int, input().split())
    wt, val = [], []

    for _ in range(N):
        w, v = map(int, input().split())
        wt.append(w)
        val.append(v)

    result.append(f"#{case} {knapsack(K, wt, val, N)}")

for _ in result:
    print(_)


output = open(f"input/{current_file}_output.txt", "r").readlines()
output = [line.strip() for line in output]

print("------------------- 오답 ------------------ ( 이 아래로 출력이 없으면 정답)")

for r, o in zip(result, output):
    if r != o:
        print(f"정답 : {o},     오답 : {r}")

풀이.

이 문제는 동적 프로그래밍으로 풀어야한다.
동적 프로그래밍으로 해결하기 위해서, 점화식을 찾아야 하며..
해당 점화식을 프로그래밍 하면 된다.
점화식을 어떻게 찾는지가 관건이다.