https://www.acmicpc.net/problem/12865
이 문제는 평범한 0-1 배낭 문제이다. 0-1 배낭 문제란, 각 물건마다 가치와 무게가 주어지고 무계 한도가 있는 배낭에 물건을 넣을 때 최대의 가치를 구하는 문제이다.
이 문제는 여러 가지 알고리즘으로 풀 수 있지만, 필자는 통상적인 다이나믹 프로그래밍 알고리즘으로 풀기로 했다. 먼저 우리가 어떤 물건 n을 넣어 최대의 가치를 구하고자 한다면, 그 물건n을 빼고 나머지 물건들의 최적해를 구하고, 그 최적해에 n을 넣느냐 마느냐 중 무엇이 더 큰지 구하면 구할 수 있다. 이를 점화식으로 나타내면
이 와 같이 나타낼 수 있다.
자세한 설명은 https://hi-guten-tag.tistory.com/160 이 블로그 링크를 참고하길 바란다. 필자는 이 블로그에서 큰 도움을 받았다. 아무튼 그러한 식으로 다이나믹 프로그래밍을 구현하면
import sys
input = sys.stdin.readline
def back(P:list):
for i in range(1,N+1):
for w in range(1,W+1):
if weights[i] > w:
P[i][w] = P[i-1][w]
else:
P[i][w] = max(P[i-1][w-weights[i]]+prices[i],P[i-1][w])
return max(max(a) for a in P)
N,W = map(int,input().rstrip().split())
weights,prices=[0],[0]
for _ in range(N):
a,b=map(int,input().rstrip().split())
weights.append(a)
prices.append(b)
P=[[0 for a in range(W+1)] for b in range(N+1)]
print(back(P))
'문제해결(PS) > 백준(BOJ)' 카테고리의 다른 글
백준 1753 최단경로 (0) | 2025.01.12 |
---|---|
백준 15686 치킨 배달 (1) | 2025.01.11 |
백준 13549 숨바꼭질3 (0) | 2025.01.08 |
백준 9251 LCS (0) | 2025.01.07 |
백준 2096 내려가기 (0) | 2025.01.07 |