1. 0-1 배낭문제

w무개, v가치를 가지고 있는 n개 물건이 존재할 경우
용량이 C인 배낭을 가지고 어떤 물건을 담아야 배낭에 담긴 물건의 가치를 최대화 할 수 있는가?
절대 배낭의 용량을 넘겨서 물건을 담을 수 없다
(NP완전문제)

1.1 정보

1. 정보

• i개의 물건
• 물건의 무게 wi
• 물건의 가치 vi
• 배낭의 용량 C

배낭문제 알고리즘

for i = 0 to n K[i,0]=0 //배낭의용량이0일때  
for w = 0 to C K[0,w]=0 //물건0이란어떤물건도고려하지않을때 
for i = 1 to n  
	for w = 1 to C //w는배낭의(임시)용량  
		if(wi > w) //물건i의무게가임시배낭용량을초과하면  
			K[i, w]=K[i-1, w]  
		else //물건i를배낭에담지않을경우와담을경우고려  
			K[i, w]=max{K[i-1, w], K[i-1, w-wi] + vi}
returnK[n, C]

1.2 예제

• 배낭의 용량 C = 10Kg
• 물건의 무게와 가치

물건	1	2	3	4
무게	5	4	6	3
가치	10	40	30	50

초기화된 행렬

행렬 작성 순서

완성된 행렬

가방의 용량 m
물건의 갯수 n
시간복잡도 O(nC)