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

# 문제 내용

백준 12865: 평범한 배낭

12865번: 평범한 배낭

 

# 알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

 

# 풀이

import sys

input = sys.stdin.readline

# 물품 수, 버틸 수 있는 무게
n, k = map(int, input().split())
data = [[0,0]]
for _ in range(n):
  # w(무게), v(가치) 순으로 추가
  data.append(list(map(int, input().split())))

# 행 : 물건 개수 (n), 열 : 가방 무게 (k) 인 2차원 배열 dp
# 물건 개수 * 가방 무게
# 1) 현재 물건이 해당 열 무게보다 많이 나가면 담을 수 없음
# 2-1) 현재 물건이 해당 열 무게보다 덜 나가면 담을 수 있음
# 2-2) 2-1에서 구한 무게와 [이전물건][현재무게]를 비교해 더 큰 값으로 채움
dp = [[0] * (k+1) for _ in range(n+1)]

for num in range(1, n+1):
  for weight in range(1, k+1):
    # 물건 개수만큼 하나하나씩 순회
    w, v = data[num]

    # 현재 측정 중인 무게가 확인 중인 물건 무게보다 무거울 경우 (담을 수 있는 경우)
    if weight >= w:
      # 확인 중인 물건의 개수와 현재 무게 위치일 때 가치값을
      # 이전 물건 개수에서 현재 무게 위치일 때 가치 값 vs 이전 물건 개수에서 (현재 무게 - 확인 중인 물건 무게) 위치에 확인중인 물건 가치 값을 더한 값 중 큰 값
      dp[num][weight] = max(dp[num-1][weight], dp[num-1][weight-w] + v)
    else:
      # 담을 수 없으므로 이전 개수의 가치값을 그대로 입력
      dp[num][weight] = dp[num-1][weight]

print(dp[n][k])

 

# References

https://claude-u.tistory.com/208

#159 백준 파이썬 [12865] 평범한 배낭 - 냅색 알고리즘