[알고리즘] - 배낭문제(Knapsack Problem)

배낭문제란?

배낭 문제는 주어진 제한된 용량의 배낭에 최대한의 가치를 가진 아이템을 넣는 방법을 찾는 문제를 의미한다. 

n개의 물건의 무게w와 가치 v에 주어질 때, 용량이 k인 배낭의 용량을 초과하지 않고 담을 수 있는 최대의 가치를 찾는 문제이다. 

배낭문제의 해결 방법

• 모든 경우 탐색 (brute-force)
  • 물건을 담는다/담지 않는다의 경우를 생각하여 2^n의 모든 조합을 탐색하는 방법은 시간 복잡도가 너무 커서 n값이 큰 경우에는 해결할 수 없다. 
• 탐욕적 알고리즘 (Greedy)
  • 단위 무게당 높은 가치부터 담는 방법.
  • 분할 배낭 문제에서는 효율적으로 동작한다. 
• 동적 프로그래밍 (Dynamic Programming)
  • 주어진 아이템과 배냥의 용량을 이용해 가능한 가치의 조합을 계산
• 브랜치 앤 바운드 (Branch and Bound) 
  • 문제의 탐색공간을 효율적으로 줄여가며(가지 치기) 최적해를 탐색

배낭문제 with Dynamic Programming

물건과 배낭의 용량을 나타내는 DP 2차원 배열을 선언한다. 

dp[i][w] : 첫 i개의 아이템 중에서 최대 w까지의 무게를 고려했을 때 얻을 수 있는 최대의 가치

 

• dp[i][w] = dp[i-1][w] 
  • 아이템 i를 선택하지 않은 경우, 이전 i-1개의 아이템으로 구성된 최대 가치와 동일함. 
• dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + values[i] )
  • 아이템 i를 선택하는 경우와 선택하지 않는 경우중 가치가 더 높은 것을 선택

배낭문제 with Dynamic Programming 코드

def knapsack_dp(values, weights, W):
	n = len(values)
    dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
    
    for i in range(1, n+1):
    	for w in range(1, W+1):
        	# 배낭에 해당 아이템을 넣을 수 있는 경우
        	if weights[i-1] <= w:
            	# 아이템을 넣지 않았을 경우와, 아이템을 넣어서 배낭의 용량이 줄고 가치가 늘어나는 것 중 최대값 선택
            	dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + values[i-1])
            # 배낭에 해당 아이템을 넣을 수 없는 경우
            else:
            	dp[i][w] = dp[i-1][w]
    return dp[n][w]