SWEA 3282. 0/1 Knapsack (Python, DP, D3)

문제 접근

0/1 Knapsack 문제는 가방에 물건을 선택하여 넣거나 (1), 선택하지 않거나(0)의 문제이다.
가치를 판단하여 넣어야 하는 문제로 Backtracking으로 풀이할 수도 있고 DP로 풀이할 수도 있다.

DP의 점화식을 세우는 것을 먼저 목표로 삼고 진행했다.

문제 풀이

DP 점화식 세우기

DP의 점화식은 아래와 같이 세울 수 있었다.
i번째의 물건을 선택하게 되면 i를 선택하기 전의 k-V의 dp값에 i번째의 물건의 가치 C를 더해준 값이 나오고, 선택하지 않는다면 전의 dp, 즉, dp[i-1][k]값을 그대로 가져올 것이다.

따라서 둘 중 더 큰 값을 dp[i][k]에 저장하면 된다. 하지만 이 때 주의할 점은 V가 k보다 클 경우에는 가방에 남은 공간이 더 작다는 소리이므로 물건을 넣을 수 없다.
따라서 이 경우는 따로 처리해줘야 한다.

dp[i][k] = max(dp[i-1][k-V[i-1]]+C[i-1], dp[i-1][k])

제출 코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, K = map(int, input().split())
    V = []
    C = []
    dp = [[0 for i in range(K+1)] for j in range(N+1)]
    for i in range(N):
        v, c = map(int, input().split())
        V.append(v)
        C.append(c) # 입력받기

    for i in range(1, N+1): # 물건 선택
        for k in range(1, K+1): # 가방의 크기 K까지의 
            if k >= V[i-1]: # 가방에 물건이 들어간다면
                dp[i][k] = max(dp[i-1][k-V[i-1]]+C[i-1], dp[i-1][k])
            else: # 가방에 물건이 들어가지 않는다면 
                dp[i][k] = dp[i-1][k]
    print(f'#{test_case} {dp[N][K]}') # 1부터 N까지의 물건중 K만큼의 크기를 만족시키는 가장 큰 값