Knapsack 알고리즘

Knapsack 알고리즘은 대학 학부 강의에서도 나올 정도로 유명한 알고리즘이다. 배낭에 물건을 담는데, 최대 가치의 물건을 담으려고 한다는 배경이 있다..

 

전형적인 다이나믹 프로그래밍(DP) 문제다. DP의 기본은 과거의 값을 사용한다는 점이다.

 

코드를 짜보기 전에 어떻게 짤 것인지 대략적인 틀을 짜야한다.

DP를 몇차원 배열로 사용할 것인가를 먼저 정해보자.

 

예를 들어 물건 4개가 있는데, 물건 하나씩 집어 무게와 가치를 본 후 넣을까 말까 고민한다고 생각해보자.

첫번째로 이 물건을 넣었을 때 갱신해줘야 하는 값은 배낭의 무게와 배낭 안에 들어있는 물건의 가치이다.

 

즉 DP[무게] = 가치로 놓을 수 있다. 즉 각 배낭의 무게에서 최대 가치를 DP에 저장한다.

그런데 이 때 각 물건을 각 배낭의 무게에서 넣을지 말지를 정해야 하므로 이차원 배열로 선언한다.

 

따라서 DP[넣을까 고민하는 물건의 무게][배낭의 무게] = 현재 배낭안의 가치로 표현할 수 있다.

 

그러면 고민할 때 무엇을 조건으로 세워야 할 지 생각해보자.

 

첫번째로 현재의 물건을 넣을 수 있는가다. 현재의 물건을 넣을 수 있는 무게가 된다면 현재 물건을 뺀 공간에 다른 물건이 있는 경우엔 두 가지 경우(dp[i-1][j-현재 물건의 무게] + 현재 물건의 가치, 현재 무게에서 이전 물건을 넣은 경우)를 비교한다.

 

현재의 물건을 절대 넣을 수 없는 무게라면, 현재 무게에서 이전 물건을 넣은 경우를 그대로 넣어준다.

 

if(현재 물건의 무게 <= 배낭의 무게){
	dp[현재 물건의 번호][배낭의 무게] = max(dp[현재 물건의 번호-1][배낭의 무게], dp[현재 물건의 번호][배낭의 무게 - 현재 물건의 무게] + 현재 물건의 가치;
else
	dp[현재 물건의 번호][배낭의 무게] = dp[현재 물건의 번호-1][배낭의 무게];

}