PS/Python
[Python] 백준 알고리즘 #12865 평범한 배낭 - dp
yoo.o
2020. 8. 12. 17:31
반응형
문제
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
풀이
dp를 사용해서 풀었다.
import sys
# N: 물품 수 / K: 무게제한
N, K = map(int, sys.stdin.readline().split(" "))
# (N+1) * (K+1) 배열 생성
dp = [[0 for _ in range(K+1)] for _ in range(N+1)]
# 물품별로 [무게(w), 가치(v)] 받기
items = []
for _ in range(N):
w, v = map(int, sys.stdin.readline().split(" "))
items.append([w,v])
# (1,1)부터 (N,K) 까지 한번씩 돌기
for i in range(1,N+1):
for j in range(1,K+1):
# items[][0] : 무게 / items[][1] : 가치
# 이 아이템의 무게가 j보다 가벼울 경우
if items[i-1][0] <= j:
# 윗 칸의 값이랑 비교해서 더 큰값을 저장
dp[i][j] = max(dp[i-1][j], dp[i-1][j-items[i-1][0]] + items[i-1][1])
else: # 윗 칸의 값 그대로 저장
dp[i][j] = dp[i-1][j]
# 표의 우측하단 끝이 답
print(dp[N][K])
반응형