동적프로그래밍 - 배낭 채우기 문제(Knapsack Problem)

* 아래 예제는 "그림으로 개념을 이해하는 알고리즘-한빛미디어"를 참고했습니다.

 

알고리즘문제 중 자주보게되는 배낭 채우기 문제 (Knapsack Problem)입니다.

 

여러가지 해법이 있지만 여기서는 동적프로그래밍을 통한 해법을 알아봅니다.  

 

 

 

---

 

4파운드의 가방을 갖고있는 도둑이 있습니다. 이 도둑은 모두 합쳐 4파운드의 물건만을 훔쳐 가지고 갈수 있습니다.

 

훔칠수 있는 물건이 아래 3개가 있다면 어떤 물건을 가방에 넣어야 최대로 많은 가치를 얻을 수 있을까요?

 

- 스테레오  :  3000달러 ,  4파운드

- 노트북     :  2000달러 ,  3파운드

- 기타        :  1500달러,   1파운드

 

 

물건이 3가지 밖에 없으므로 물건의 조합 (2^3 = 8)으로 최적해를 찾을 수 있습니다.

 

스테레오-노트북 : 무게초과

스테레오-기타    : 무게초과

스테레오           : 3000달러

노트북   -기타    : 3500달러

노트북              : 2000달러

기타                 : 1500달러

물건없음           :      0달러

 

하지만 물건의 갯수가 증가하면 조합의 수도 늘어나므로 O(2^n)로 점점 느려집니다. 

 

이 문제를 풀기위해 동적프로그래밍을 사용합니다. 동적프로그래밍은 하위의 작은 문제를 풀고 이를 이용해서 더 큰 문제를 풀어가는 문제 해결방법입니다.

아래같이 물건들중 최소무게인 1파운드 단위로 가방 크기인 4 파운드까지 표시할 수 있는 표를 만들고 채워나가는 방법을 사용합니다.

 

	1 lbs	2 lbs	3 lbs	4lbs
기타
스테레오
노트북

 

첫번째로 기타만 넣는다고 가정하면 1파운드이므로 가방이 1파운드이상이면 가방에 들어갑니다. 넣을 수 있는 모든 가방에 그 가치를 입력합니다.

 

	1 lbs	2 lbs	3 lbs	4lbs
기타	1500$	1500$	1500$	1500$
스테레오
노트북

 

두번째로 스테레오를 넣는 경우입니다.  스테레오는 4파운드이므로 1파운드,2파운드,.3파운드 가방에는 이전에 넣은 기타빡에 넣을수 없습니다.(이전열의 최대값). 4파운드 가방에는 기타보다 더 가치가 높은 스테레오를 담습니다.

 

	1 lbs	2 lbs	3 lbs	4lbs
기타	1500$	1500$	1500$	1500$
스테레오	1500$	1500$	1500$	3000$
노트북

 

세번째로는 노트북을 넣습니다. 노트북은 3파운드이므로 1파운드,2파운드 가방에는 이전 최대값인 1500$(기타)를 넣을수 있습니다.

3파운드 가방에는 기타를 넣는것보다 노트북(3파운드)를 넣는것이 유리합니다.

4파운드 가방에는 노트북(3파운드)와 남은 1파운드를 채울수 있는 최대값인 기타를 채우는것이 최대 가치를 넣는 방법입니다.

 

	1 lbs	2 lbs	3 lbs	4lbs
기타	1500$	1500$	1500$	1500$
스테레오	1500$	1500$	1500$	3000$
노트북	1500$	1500$	2000$	3500$

 

 

 

이것을 일반화하면 

 

                   1. 이전에 구한 CELL[i-1][j] 의 최대값

CELL[i][j] 의 최대값

                   2. 현재 물건의 가치 + 남은 공간의 가치(CELL[i-1][j-물건의 무게])

 

EX) CELL[3][4]를 예로 들면

     1. 이전에 구한  CELL[2,4]는 3000$

     2. 현재 물건의 가치( 2000$)  + 남은공간의 가치( CELL[2][1] == 1500$) 는 3500$

 

 

 

이것을 파이썬 코드로 구현하면 아래와 같습니다.

 

 

def solutions(sizeOfBag , valueList, weightList ):
	maxValue = 0
    bagList = []
    # 격자생성
    # 공간이 없다는 의미를 0번 INDEX로 사용하기 위해 방하나 더 만듬
    bagList = [ [0]*(sizeOfBag+1) for _ in range(len(valueList)+1)]
    
    # 인덱스를 맞추기 위해 valueList와 weightList도 맨 앞에 0인 값을 추가
    valueList = [0] + valueList
    weightList = [0] + weightList
    
    # i,j는 1부터 시작
    # i = 물건의 인덱스
    # j = bag의 크기인덱스 (값을 비교할때는 +1)
    # valueList[i] : 현재 물건의 가치
    # weightList[i] : 현재 물건의 무게
    for i in range(1,len(valueList)):
    	for j in range(1,sizeOfBag+1):
        	if j >= weightList[i] :
            	bagList[i][j] = max(bagList[i - 1][j],bagList[i-1][ j- weightList[i]] + valueList[i] )
            else:  # 현재 물건이 안들어가면 기존 물건중 최고
            	bagList[i][j] = bagList[i - 1][j]
            
    return bagList[len(valueList)-1][sizeOfBag]
    
 def main():
 	sizeOfBag = 4
    valueList = [1500, 3000, 2000]
    weightList = [1,4,3]
    print(solutions(sizeOfBag,valueList,weightList))
    sizeOfBag = 6
    valueList = [1500, 3000, 2000,4000]
    weightList = [1,4,3,2]
    print(solutions(sizeOfBag,valueList,weightList))
    
if __name__ == "__main__":
	main()