[백준/파이썬(Python)] 12865: 평범한 배낭 Gold 5 (냅색 알고리즘)

💌문제

---

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

💌풀이

---

DP를 쓰는 기본적인 문제이다. 냅색 알고리즘은 주어진 가방의 용량을 초과하지 않으면서 가치가 최대가 되도록 물건을 선택하는 최적화 문제이다.

예를 들어, 용량이 10인 가방에 물건들을 담을 때, 물건들의 가치를 최대화하려면 어떤 물건을 선택해야 하는지 결정해야 한다.

Fractional Knapsack 알고리즘과 0-1 Knapsack 알고리즘 두 가지 종류가 있다.

두 개의 알고리즘 모두 주어진 용량을 초과하지 않으면서 가치가 최대가 되도록 물건을 선택하는 최적화 문제인 배낭 문제를 해결하는 알고리즘이다.

하지만 Fractional Knapsack 알고리즘은 그리디 방식으로 문제를 해결할 수 있고, 0-1 Knapsack 알고리즘은 DP 방식으로 문제를 해결해야 한다.

 

Fractional Knapsack 알고리즘은 물건을 쪼개서 선택할 수 있을 때, 무게와 가치의 비율이 높은 물건부터 선택한다.

반면에 0-1 Knapsack 알고리즘은 물건을 쪼갤 수 없는 경우, 모든 물건이 선택되거나 선택되지 않는 경우로 나뉘어서 최적해를 구하는 방법이다.

 

여기서 물건을 쪼개서 선택할 수 있다는 말은, 각 물건이 무게와 가치를 가지고 있고, 이 무게를 부분적으로 선택할 수 있다는 의미이다.

 

예를 들어, 가방에 담을 수 있는 무게가 10kg이고 3개의 물건이 있을 때 각 물건의 무게와 가치가 다음과 같다고 가정한다.

 

• 물건 1: 무게 5kg, 가치 100
• 물건 2: 무게 3kg, 가치 80
• 물건 3: 무게 2kg, 가치 50

 

여기서 Fractional Knapsack 알고리즘은 물건 1을 선택하고, 가방에 5kg을 채웠다. 이때, 물건 1을 두 개로 쪼개서 2.5kg만 선택할 수 있다. 그래서 물건을 부분적으로 선택할 수 있기 때문에 물건을 쪼개서 선택한다고 한다.

반면, 0-1 Knapsack 알고리즘에서는 각 물건을 하나의 덩어리로만 선택할 수 있기 때문에 물건을 쪼갤 수 없다. 따라서, 선택하는 물건의 무게 합이 가방의 무게를 초과할 경우 해당 물건을 선택하지 않고 다른 물건을 선택하게 된다.

보통의 알고리즘 문제에서는 주로 0-1 Knapsack이 많이 나오긴 한다.

https://chanhuiseok.github.io/posts/improve-6/

[알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)

https://hongcoding.tistory.com/50

[백준] 12865 평범한 배낭(Python 파이썬)

가장 이해하기 힘든 부분이, 현재 물건을 배낭에 넣는 부분에서, 현재 넣을 무게만큼 배낭에서 뺀다고 하는 부분이다. 즉, dp[i][j-w]부분이라 위의 블로그 등을 많이 찾아봤다.

 

현재 넣을 무게와 똑같은 무게의 물건이 없으면 어떻게 빼는가? 애초에, 현재 물건을 넣게 되는데 왜 무게만 빼고 밸류는 더해주는가?

→ 현재 넣을 물건의 무게만큼 뺀 배낭에는 그 무게의 배낭이 가지는 최대의 가치가 저장되어 있다. 즉, DP를 이용해서 현재 가질 수 있는 최대 가치를 계속 더해주는 것이다. 왜냐면 우리는 현재 물건을 넣지 않을 때는 이전 상태를 유지해서 계속 DP에 저장해줄 것이기 때문이다.

 

💌파이썬 코드

---

n,k=map(int,input().split())
bag=[[0,0]]
dp=[[0]*(k+1) for _ in range(n+1)] # n= 물건 갯수 k=무게 제한

for i in range(n):
	bag.append(list(map(int,input().split())))
for j in range(n):
	for j in range(1,k+1):
		w=bag[i][0]
		v=bag[i][1]
		if j<w: # 현재 dp 무게가 현재 물건의 무게보다 작아서 물건을 담지 못한다.
			dp[i][j]=dp[i-1][j] # 이전 상태=이전 물건을 선택한 상태를 유지한다.
		else: # 현재 물건을 담을 수 있다.
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v) # 이전상태와 현재 물건을 넣었을 때의 밸류값을 비교해서 더 큰 걸 저장한다.
print(dp[n-1][k])