0-1 배낭 문제 - 파이썬

다이나믹 프로그래밍(Dynamic Programming)의 대표 문제인 배낭 문제에 대해서 분석해본다. 

다음과 같이 쪼갤 수 없는 짐이 있고 이를 배낭에 넣을 때 어떤 것이 가장 효율적일까?

 

짐의 개수

# (가격, 무게)
cargo = [
    (4, 12),
    (2, 1),
    (10, 4),
    (1, 1),
    (2, 2),
]

 

 

전체 코드

def zero_one_knapsack(cargo):
    capacity = 16
    pack = []

    # cargo = (가격, 무게)
    for i in range(len(cargo) + 1):
        pack.append([])
        for c in range(capacity + 1):
            cargo_price, cargo_cap = cargo[i - 1]
            if i == 0 or c == 0:
                pack[i].append(0)

            elif cargo_cap <= c:
                pack[i].append(
                    max(cargo_price + pack[i - 1][c - cargo_cap], pack[i - 1][c])
                )
            else:
                pack[i].append(pack[i-1][c])
               
    return pack[-1][-1]

 

배낭의 용량이 15kg이라고 했을 때 위의 코드를 분석해 보자. 

먼저 i=0일 때 다음 코드로 인해 pack의 첫번째 리스트는 다음과 같이 저장된다.

if i == 0 or c == 0:
    pack[i].append(0)

 

이제 i=1일 때부터 살펴 본다. 먼저 c가 0~11까지인 경우이다. c가 0~11일 때 cargo_cap > c 이므로 바로 이전 배낭의 저장된 price값으로 저장한다. 

else:
	# cargo_cap > c (12 > 0~11)
    pack[i].append(pack[i-1][c])

 

 

cargo_cap >= c인 경우는 다음과 같다. 현재 c에 해당하는 가격은 현재 짐 가격과 남은 배냥 용량에 해당하는 값을 더해서 구할 수 있다. 남은 배낭 용량 = 배낭 용량 - 현재 짐 무게이고, 남은 배낭 용량에 해당하는 가격을 이전 pack에서 계산할 수 있다. i=1인 경우 용량이 12이고, 남은 배낭용량은 각각 0,1, 2,3인데 pack[i-1][0~3] = 0이므로 가격 4만 테이블에 저장된다.

elif cargo_cap <= c:
	# cargo_price + pack[i-1][0~3] 
    # pack[i-1][12~15]=0 
    pack[i].append(
        max(cargo_price + pack[i - 1][c - cargo_cap], pack[i - 1][c])
    )

 

i=2의 경우도 살펴본다. cargo_cap=1이므로 c = 0을 제외한 c=1 부터 배낭에 짐을 넣을 수 있다.

이후 c=1~11까지 cargo_cap(=2) + pack[i-1][0~10](=0) -> 2 + 0 -> 2 값을 저장한다. pack[i-1][0~10]보다 해당 값이 크므로 테이블은 다음과 같이 저장된다.

c=12에서는 이전 짐의 가격 pack[i-1][12]가 4로 2보다 크다. 따라서 해당 값을 추가한다.

c=13~15까지 배낭의 가격은 cargo_price(=2) + pack[i-1][12~14](=4) = 6이므로 해당 값을 테이블에 추가한다.

 i=3~5까지 해당 로직을 반복하면 다음과 같다.

정리

열 길이는 용량 + 1,  행의 길이는 짐의 개수 + 1인 2차원 배열 pack을 생성한다. 생성 절차는 다음과 같다.

짐의 개수 len(cargo) + 1만큼 순회하며 순회하는 포인터는 i이다. 각 순회할 때마다 행을 생성한다. 처음 행은 모두 0으로 초기화해서 추가한다. 이 후 i=1부터 본격적으로 행 데이터를 생성한다. cargo[i-1]은 행 i에서 사용할 가격, 용량을 가진다. 각각을 cargo_price, cargo_cap이라고 한다.

용량 c를 포인터로 순회할 때 cargo_cap > c이면 배낭에 짐이 들어갈 수 없다. 이전 행에 해당하는 용량의 가격을 그대로 추가한다. cargo_cap <= c이면 배낭에 짐이 들어갈 수 있다. 현재 가격 cargo_price와 남은 용량 c - cargo_cap에 해당하는 이전 배낭에 가격

pack[i-1][c - cargo_cap]을 더하면 현재 배낭에 들어갈 가격을 계산할 수 있다. 이 가격과 이전 배낭에 저장된 용량의 가격 pack[i-1][c]을 서로 비교해서 큰 값을 pack[i][c]에 저장한다. 이를 통해 각 행에는 용량에 해당하는 최대값이 저장된다.

위의 연산을 반복하면 가장 우측, 하단에는 용량에 해당하는 최대 가격을 구할 수 있다.

 

이해하기 어려웠던 부분

전형적인 타뷸레이션 문제였으나 어떻게 테이블을 생성하여 추가해 나갈지 아이디어를 생각하기 어려웠다. 각 테이블에 용량에 해당하는 가격을 이전 행의 데이터를 참고하여 계산 후 순차적으로 추가하며, 다음 행에 계산을 할 수 있도록 하는 방식인데 DP로 문제를 접근한다고 하면 다음 코드를 꼭 기억할 필요가 있을 듯 하다.

elif cargo_cap <= c:
    pack[i].append(
        max(cargo_price + pack[i - 1][c - cargo_cap], pack[i - 1][c])
    )

각 행 마다 항상 최대 가격을 저장하는 부분인데, 현재 가격과 남은 용량에 해당하는 가격을 도출하는 부분에 대해 이해한다면 나머지는 크게 어렵지 않을 듯하다