동적 계획법과 Knapsack 문제

🗯️ knapsack 문제

가능한 조합의 최적의 경우를 찾는 문제입니다.

배낭이 주어지고 담을 수 있는 것들의 무게와 최대가치가 주어졌을때 주어진 무게를 넘지 않으면서 최대의 가치를 담을 수 있도록 해결하는 문제를 말합니다.

 

🔎 DP로 풀어가면 쉽게 해결할 수 있는 문제로, DP문제의 대표적인 유형입니다.

아래의 간단한 대표 문제로 살펴보면

 

(문제)

최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 
이 보석들의 가치는 각각 4,5,10,11,13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있다는 뜻입니다.

 

 

(입력)

첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다.

두 번째 줄부터 각 보석의 무게와 가치가 주어진다.

가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.

 

 

(출력)

첫 번째 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다.

 

 

(풀이)

import sys

input=sys.stdin.readline

cnt,weight=map(int,input().split())
dy=[0]*(weight+1)

for _ in range(cnt):
    w,v=map(int,input().split())
    for j in range(w,weight+1):
        dy[j]=max(dy[j],dy[j-w]+v)

print(dy[weight])

 

 

(설명)

dy[x]의 값은 배낭이 x 무게를 가질때 가지는 최대가치를 말합니다.

dy의 업데이트 시점은

• 기존의 dy[j]의 값과 새로 탐색한 보석 w가 새로 들어온다고 했을 때를 비교해서 업데이트 해주면 됩니다.
• 여기서 새로 들어온 보석의 무게(w)가 3이라고 하고 보석의 가치(v)가 8이라고 하면, 새로 들어온 보석을 제외한 최대 무게 dy[j-w]에다가 v의 값을 더해주면 됩니다.

 

 

 

 

➕ 대표문제

백준 12865번 평범한 배낭  https://www.acmicpc.net/problem/12865

 

 

 

참고

---

https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8/dashboard