[백준/Python] 12865 평범한 배낭

[백준/Python] 12865 평범한 배낭

정답 코드 및 설명

전체 코드

N, K = map(int, input().split())  # 물품의 수 N, 가방에 넣을 수 있는 무게 K 입력 받기
Things = []  # 물품의 무게와 가치를 저장할 배열

# 입력 받아서 Things에 삽입
for i in range(N):
    w, v = map(int, input().split())  # 물품의 무게 w와 가치 v 입력 받기
    Things.append((w, v))

# 해를 담을 Pack 배열 초기화, 최적해는 Pack[N][K]
Pack = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

# 동적 프로그래밍으로 Pack 배열 채우기
for i in range(1, N + 1):
    for k in range(1, K + 1):
        if Things[i-1][0] > k:  # 물건 i의 무게가 임시 배낭 용량을 초과하면
            Pack[i][k] = Pack[i-1][k]
        else:  # 물건 i를 배낭에 담지 않을 경우와 담을 경우 각각을 고려
            Pack[i][k] = max(Pack[i-1][k], Pack[i-1][k - Things[i-1][0]] + Things[i-1][1])

print(Pack[N][K])  # 모든 물건의 가치 합(최적해) 출력

코드 설명

위 문제는 물건, 물건의 무게, 물건의 가치, 들 수있는 최대 용량, 총 4개의 요소가 있다.

이를 생각했을때, 최대로 들 수 있는 용량을 고려하는 게 아닌 0 부터 최대로 들 수 있는 용량을 고려하되 물건 1 부터 i 까지 고려하는 방법을 사용한다.

Pack[i,k] 가 의미하는 것은 물건 1부터 i까지 고려하고, 최대 용량이 k 일때 최대 가치를 의미한다.

문제의 정답은 Pack[N][K] 가 되는 것이다.

먼저 최대 들 수 있는 용량이 0 이라고 했을 때 Pack[i,0] = 0 으로 초기화 해준다. 넣을 수 있는 물건이 0 이므로 Pack[0,w] 도 0으로 채워 준다

다음으로 for 문을 생성하는 데 이중 포문을 사용한다. 제일 바깥쪽 for 문은 물건 1부터 i 까지 순회하고 그 다음 for 문은 최대 들 수 있는 용량이 1부터 K 까지 순회한다.

후에 if 문을 통해 지금 선택된 물건 i 의 무게가 현재 넣을 수 있는 무게 k 를 초과한다면 Pack[i,w] 는 이전 값이 유지된다. Pack[i-1,w]
현재 선택된 물건 i 의 값이 넣을 수 있는 무게라면 Pack[i,w] 는 물건 i를 가방에 넣지 않을 경우와 넣을 경우를 비교해서 더 가치있는 것을 선택하면 된다.

Pack[i,w] = Pack[i][k] = max(Pack[i-1][k], Pack[i-1]k - Things[i-1][0]] + Things[i-1][1])

이중 for 문을 전부 순회했다면 맨 끝에 있는 값이 정답이 된다.