알고리즘 - 배낭 채우기

배낭 채우기

배낭 문제의 순환 관계식

• 0-1 배낭 문제에서 주어진 문제와 부분 문제 사이의 관계
• 배낭의 가치 => $A(k,w)$ 로 나타낼 수 있음

기반 상황

• 배낭에 넣을 물건이 없다면(k=0), 배낭 용량과 상관없이 최대가치 0 $A(0,w)=0$
• 배낭의 용량이 0이라면(w=0), 배낭 최대가치는 0 $A(k,0)=0$

일반 상황

• Case1: 만약 k번째 물건의 무게 wgt_k가 남은 배낭 용량 w보다 크면, 어차피 배낭에 넣을 수 없음, 따라서 $A(k,w) = A(k-1,w)$가 됨

• Case2: k번째 물건을 배낭에 넣을 수 있다면 $wgt_k$ 가 w이하인 경우
• $E_k$를 배낭에 넣는 경우 $val_k + A(k-1, w-wgt_k)$
• $E_k$를 배낭에 넣지 않는 경우 $A(k-1, w)$

분할 정복 알고리즘

(0-1 배낭 채우기(분할정복))

def knapSack_bf(W, wt, val, n): 
    if n == 0 or W == 0 :       # 기반 상태. 물건이 없거나 용량이 0이면
        return 0                # 전체 가치 합은 0이 됨
  
    if (wt[n-1] > W):                           # 넣을 수 없음
        return knapSack_bf(W, wt, val, n-1)     # 나머지 항목들로 다시 처리
  
    else: 
        valWith = val[n-1] + knapSack_bf(W-wt[n-1], wt, val, n-1)
        valWithout = knapSack_bf(W, wt, val, n-1)
        return max(valWith, valWithout)

• 지수 시간이 걸리는 매우 비효율적인 알고리즘
• 만약 물건의 무게가 실수로 표현된다면 다른 방법이 별로 없음

동적 계획법에 의한 0-1 배낭 문제 해법

• 물건의 무게와 배낭의 용량을 모두 정수로 제한

테이블 설계

• (n+1) x (W+1) 의 2차원 배열 형태

배낭 채우기 알고리즘

def knapSack_dp(W, wt, val, n): 
    # 테이블 생성 및 0으로 초기화(W=0, n=0인 경우 모두 0)
    A = [[0 for x in range(W + 1)] for x in range(n + 1)] 
  
    for i in range(1, n + 1): 
        for w in range(1, W + 1): 
            if wt[i-1] > w:         # case1: i번째 물건이 배낭 용량을 초과함
                A[i][w] = A[i-1][w] # i번째 물건을 무시하고 나머지로 계산(계산되어 있음)
            else :                  # case2: i번째 물건이 배낭 용량 이하임
                valWith = val[i-1] + A[i-1][w-wt[i-1]]  # case2.1: 넣는 경우
                valWithout = A[i-1][w]                  # case2.2: 빼는 경우
                A[i][w] = max(valWith, valWithout)      # 더 큰 값 선택
  
    return A[n][W]                  # 최종 결과가 저장됨

0-1 배낭 채우기 테스트 프로그램

val = [60, 100, 190, 120, 200, 150] 
wt = [2, 5, 8, 4, 7, 6] 
W = 18
n = len(val) 
print("0-1배낭문제(분할 정복): ", knapSack_bf(W, wt, val, n)) 
print("0-1배낭문제(동적 계획): ", knapSack_dp(W, wt, val, n)) 

실행 결과

0-1 배낭문제(분할 정복): 480
0-1 배낭문제(동적 계획): 480

복잡도 분석

• 채워야 할 칸의 수 n x W 이므로 전체 시간복잡도 $O(nW)$이다
• 완전 탐색이나 분할 정복 알고리즘보다 월등함
• 공간 복잡도 $O(nW)$
• 물건의 무게가 실수로 주어지면 테이블 크기가 거의 무한대가 되어 적용 불가