코드

n, k = map(int, input().split())

# 가지고갈 물건의 무게와 가치를 담을 리스트
# 처음 0,0 값을 넣어서 인덱스를 편하게 관리할 수 있음
ob = [[0, 0]]

# DP 테이블
# k+1만큼 0을 넣고, n+1만큼 행을 갖게 만듬
# 마찬가지로 인덱스를 편하게 관리할 수 있음
pack = [[0 for _ in range(k+1)] for _ in range(n+1)]

for _ in range(n):
    # w, v 입력받음
    ob.append(list(map(int, input().split())))

# 1~n, 1~k 만큼 반복
for i in range(1, n+1):
    # j : 배낭에 담을 수 있는 최대 무게
    for j in range(1, k+1):
        
        # 무게와 가치를 뽑아냄
        w = ob[i][0]
        v = ob[i][1]
        
        # i번째 물건의 무게보다 작다 => 배낭이 담을 수 있는 무게를 초과했다
        # 당연히 못 넣으므로 그전 DP 테이블의 값을 그대로 가져옴
        if j < w:
            # 바로 전까지의 누적 v값을 그대로 가져옴
            pack[i][j] = pack[i-1][j]
        # 크거나 같다 => 배낭에 추가로 더 넣을 수 있다
        else:
            # pack[i-1][j-w] + v의 의미
            # i번째 물건을 넣지 않는 경우, 배낭에 담을 수 있는 최대 무게는 
            # i번째 물건의 무게를 뺀 나머지가 되므로 => j-w가 된다
            # pack[i-1][j-w]는 i번째 물건을 넣기 전까지의 최대 효용 가치가 되고
            # 여기에 v (i번째 물건의 가치)를 더해주면 원하는 값을 구할 수 있다
            
            # 위의 주석 과정을 넣은 경우와 넣지 않은 경우 둘 중 더 큰 값을 DP 테이블에 업데이트 해줌
            pack[i][j] = max(pack[i-1][j], pack[i-1][j-w] + v)
            
print(pack[n][k])

문제 해설

DP 문제에서 매우 유명한 냅색(배낭) 문제. (냅색 문제 나무위키 참고)

이 문제를 접하기 전까지 이 유형의 문제가 유명하다는 것 조차 알지 못했다 ㅠㅠ

풀이 순서

  1. DP 테이블을 2차원 리스트로 생성하여 보유한 물건들을 순서대로 최대 허용 무게만큼 하나씩 넣어주면서 최대 효용 가치를 계산한다
  2. 무게가 초과되면 이전 아이템을 빼거나 기존 그대로 가지는 방법 중 하나를 선택하여 DP 테이블을 계속해서 업데이트 해준다

위 두 과정을 반복하여 거쳐 마지막 DP 테이블까지 모두 업데이트 시키면 최종적으로 가치합의 최댓값을 구할 수 있다.

댓글남기기

참고