[Dynamic Programming] 0-1 배낭 문제

0 - 1 배낭 문제

다이나믹 프로그래밍의 대표적인 문제 중 하나로, 한정된 용량의 배낭에 최대 가치를 담을 수 있도록 최적의 선택을 찾는 문제이다.

배낭 문제는 짐을 쪼갤 수 있는지 여부로 그리디로 풀 수 있는지, DP(Dynamic Programming)으로 풀 수 있는지 나뉜다. 0-1 배낭 문제는 짐을 쪼갤 수 없는 경우에 해당하며, 다이나믹 프로그래밍으로 풀이 가능하다.

 

Bottom-up

class Solution:
    def zero_one_knapsack(self,cargo:list):
        capacity = 15 # 최대 용량
        pack = [] # 가치 저장
        for i in range(len(cargo)+1): # len(cargo) = 5
            pack.append([])
            for c in range(capacity+1):
                if i == 0 or c == 0: # index 0은 사용하지 않으므로 0 삽입
                    pack[i].append(0)
                elif cargo[i-1][1] <= c: # cargo[i-1][1] = 용량
                    pack[i].append(max( # 가치가 큰 것을 선택
                        cargo[i-1][0] + pack[i-1][c - cargo[i-1][1]], 
                        pack[i-1][c]
                    ))
                else:
                    pack[i].append(pack[i-1][c])
        print(pack[-1][-1])

if __name__ == "__main__":
    s = Solution()
    cargo = [ # (가치, 용량)
        (4, 12),
        (2, 1),
        (10, 4),
        (1, 1),
        (2, 2)
    ]
    s.zero_one_knapsack(cargo)

 

pack이라는 리스트에 6 x 16 행렬 형태의 중간 결과 테이블이 생성된다. 행렬은 짐의 최대 개수 + 1, 배낭의 최대 용량 + 1의 계산으로 6 x 16 형태가 된다. 이 테이블에는 짐의 개수와 배낭의 용량에 따른 최댓값이 담긴다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0	0	0	4	4	4	4
2	0	2	2	2	2	2	2	2	2	2	2	2	4	6	6	6
3	0	2	2	2	10	12	12	12	12	12	12	12	12	12	12	12
4	0	2	3	3	10	12	13	13	13	13	13	13	13	13	13	13
5	0	2	3	4	10	12	13	14	15	15	15	15	15	15	15	15

 

이 테이블의 세로 축은 짐의 개수, 가로축은 배낭의 용량이다. 즉 짐이 4개가 있을 때는 차례대로 ($4, 12kg), ($2, 1kg), ($10, 4kg), ($1, 1kg)일 것이고, 배낭의 용량이 4kg이라면 최댓값은 10이 된다. 이렇게 마지막 위치인 5 x 15까지 이동한 총 5개의 짐, 용량이 15인 배낭의 최댓값은 15가 된다.