Knapsack 알고리즘

여러 제한 사항들에 따라 문제 유형을 분류해 보았다. 풀면서 익혀보자.

 

1. 가방문제 (최대, 보석 제한X)

 

먼저 이러한 dp 테이블을 두자. (0으로 초기화)

i번째 칸이 의미하는것은 가방에 i(kg)까지 담을 수 있을 때 최대 가치이다.

 

그러면 5kg짜리 보석만 있다고 생각하자. dp[5]부터 채우면 다음과 같다.

i번째 칸에 5kg을 담는다고 가정했으니까 인덱스는 5빼주고 그 dp[i-5]에서 v(12)의 가치를 더해준다. 

마찬가지로 이번에 3kg짜리 보석도 함께 있다고 생각해보자

dp[i]=max(dp[i],dp[i-w]+v) 로 점화식을 세울 수 있겠다.

예를 들어 dp[6]의 경우에는 기존의 dp[6](=12)보다 dp[6-3]+8(=16)이 더 크므로 바꿔준다.

 

이런식으로 나머지 6,4도 적용해 최종적으로 dp[11]을 구하면 된다. 

 

코드 

n,m=map(int,input().split())

dp=[0 for _ in range(m+1)]
for i in range(n):
	w,v=map(int,input().split())
	for j in range(w,m+1):
		dp[j]=max(dp[j],dp[j-w]+v)
    
print(dp[m])

 

2. 동전 교환(최소, 동전 제한X)

 

마찬가지로 dp테이블을 둔다. 이 때 최소 동전의 갯수를 구하므로 최대값으로 초기화시켜준다.

dp[i]가 의미하는것은 i원을 거슬러주는데 사용된 동전의 최소 갯수이다. 

만약 1원짜리로만 돈을 거슬러준다하면 

2원까지 함께 사용한다면

점화식은 dp[i]=min(dp[i-coin[j]]+1,dp[i])

최종 5원까지 사용했을때

 

코드

n=int(input())
coin=list(map(int,input().split()))
m=int(input())
dp=[1000 for _ in range(m+1)]
dp[0]=0
for i in range(n):
	for j in range(coin[i],m+1):
		dp[j]=min(dp[j],dp[j-coin[i]]+1)
    
print(dp[m])

 

3. 최대 점수 구하기 (한 유형당 한개만!)

 

앞에 문제하고 차이가 있다면 문제를 여러번 풀 수 있는것이 아닌 한번만 풀 수 있다는 것이다.

그러다보니 앞에 어떤 선택을 했냐에 따라 뒤에 선택값이 달라질 수 있으므로 

2차원 dp 배열을 두자

dp[i][j] 테이블의 의미는 i번째 문제까지 적용했을때  나한테 j분의 시간이 주어졌다면 얻을 수 있는 최대 점수이다. 

1번째칸에서 5분부터 시작해 10을 채워나간다. 

이때 우리가 따라서 참조해야할것은 그 전칸(왼쪽칸)이 아닌 dp[i-1][j-pt]번째 행이다. (dp[1][10]은 20이 아닌 10이다. 중복 X이므로)

따라서 dp[1][10]은 dp[i][j]=dp[i-1][j-t]+v이다.

 

2번째 행을 시작하기 전에 그전에 적용된 것을 복사한다. 

dp[2][12] 부터 시작한다하면 dp[1][0]에서 25를 더한다.

이때 25가 10보다 크므로 dp[2][12]는 25로 채워준다. dp[2][17]같은 경우에는 dp[1][5]에서 25를 더하므로

35가 된다. (dp[2]는 2번 문제까지 적용된)

3행도 마찬가지로 2행 것을 복사한 다음에 똑같이 해주면 다음과 같이 채워진다.

그렇게 해서 최종적으로 dp[5][20]을 구하면 된다.

이렇게 2차원으로 해도 되지만 메모리 낭비가 심하다... 1차원으로 해결하는 방법도 있다.

여기서 dp[i]는 i분이 주어졌을 때 얻을 수 있는 최대 점수

이번에는 뒤에서부터 값을 매긴다. dp[20]은 dp[15]에서 10을 더한 값

즉 dp[i-t]+v=dp[i]

2번째 행도 마찬가지로 dp[20]에서 t를 뺀 행인 dp[12]에서 25를 더하는 식으로

3번째 행도 마찬가지로 dp[20]에서 8을 뺀 dp[12]에서 15를 더하면 dp[20]은 40이 된다. 

앞의 값을 참조하고 뒤에 값을 안보기 때문에 중복될 여부가 없다. 

n,m=map(int,input().split())
dp=[0 for _ in range(m+1)]
for i in range(n):
	ps,pt=map(int,input().split())
	for j in range(m,pt-1,-1):
		dp[j]=max(dp[j],dp[j-pt]+ps)
 
print(dp[m])

 

4. 그 외의 백준 문제들..

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

풀이: https://didu-story.tistory.com/440

[백준] (Python) 2293번 - 동전1 (골드5, dp)

 

출처: it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++)