[BOJ] 12865번: 평범한 배낭 - Python

백준의 [단기간 성장] 문제집을 파이썬으로 풀고 있다.
https://www.acmicpc.net/workbook/view/4349

문제

https://www.acmicpc.net/problem/12865

문제 풀이

앞에서 계산했던 다른 칸의 값을 이용해서 현재의 최적값을 찾아야하기 때문에 DP를 이용했다.
이 문제는 DP의 고전인 배낭 문제(Knapsack Problem)이다.

배낭 문제는 두 가지 유형이 있다.

• 부분 배낭문제(Fractional Knapsack Problem) : 금과 같이 나누어 담을 수 있는 경우
• 0-1 배낭문제(0-1Knapsack Problem) : 물건을 담거나 안 담거나

요 문제는 물건을 나누어 담을 수 없으므로 0-1 배낭문제이다.

알고리즘

if w_arr[i] > j:
    dp_arr[i][j] = dp_arr[i-1][j]

else:
    dp_arr[i][j] = max(dp_arr[i-1][j], dp_arr[i-1][j-w_arr[i]]+v_arr[i])

x축을 배낭이 버틸 수 있는 무게, y축을 물건의 개수로 하는 2차원 배열을 생성한 뒤, 각 원소마다 위의 알고리즘을 적용한다.

알고리즘은 다음과 같다.

만약 현재 물건의 무게가 배낭의 용량보다 크다면, 지금 물건을 포기하고 이전 물건을 담을 때까지의 가치합을 저장한다.

물건의 무게가 배낭의 용량보다 작거나 같다면 가치의 비교를 한다.
이전 물건을 담을 때까지의 가치합 vs (내 물건을 담을 공간을 남긴만큼의 이전 가치합 + 현재 물건 가치합)

소스 코드

import sys

N, K = tuple(map(int, sys.stdin.readline().split()))  # 물품의 수, 버틸 수 있는 무게
w_arr =[0]*(N+1)
v_arr = [0]*(K+1)

for i in range(1, N+1):
    w_arr[i], v_arr[i] = tuple(map(int, sys.stdin.readline().split())) # 물건의 무게와 가치 초기화

dp_arr = [[0]*(K+1) for _ in range(N+1)]

max_value = -sys.maxsize  # 가치합의 최댓값

for i in range(1, N+1):
    for j in range(1, K+1):

        if w_arr[i] > j:  # 현재 물건의 무게가 배낭무게보다 크면
            dp_arr[i][j] = dp_arr[i-1][j]  # 이전 물건을 담을 때까지의 가치합을 저장

        else:  # 이전 물건을 담을 때까지의 가치합 vs 내 물건을 담을 공간을 남긴만큼의 이전 가치합과 + 현재 물건 가치합
            dp_arr[i][j] = max(dp_arr[i-1][j], dp_arr[i-1][j-w_arr[i]]+v_arr[i])

    if dp_arr[i][K] > max_value:
        max_value = dp_arr[i][K]

print(max_value)

입력에 대한 dp 테이블을 출력한 결과는 다음과 같다.