[Python] 백준 12865 평범한 배낭

1. 문제 링크

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

12865번: 평범한 배낭

2. 문제 요약

 

3. 아이디어 정리

3-1. 냅색 문제 개념

한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

dp[i][j] = max(현재 물건 가치 + dp[이전 물건][현재 가방 무게 - 현재 물건 무게], dp[이전 물건][현재 가방 무게])

예시를 표로 만들어 보면 아래와 같다.

 

4. 문제 풀이

4-1. 내 풀이

import sys

n, k = map(int, sys.stdin.readline().split())  # 물품의 수, 버틸 수 있는 무게
arr = [(0, 0)]
chart = [[0] * (k + 1) for _ in range(n + 1)]
for _ in range(n):
    w, v = map(int, sys.stdin.readline().split())
    arr.append((w, v))

for i in range(1, n + 1):   # 물건 하나씩
    for j in range(1, k + 1):  # 1~k무게까지 표 작성
        w = arr[i][0]
        v = arr[i][1]
        if j < w:   # 해당 물건이 더 큰 경우, 이전 표값으로 넣기
            chart[i][j] = chart[i - 1][j]
        else:   # 해당 물건이 들어가는 사이즈인 경우
            chart[i][j] = max(chart[i - 1][j], v + chart[i - 1][j - w])    # 이전 값과 비교

print(chart[n][k])

 

 

5. 결론

• dp 문제