백준 12865 평범한 배낭

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))