알고리즘: Knapsack(배낭 알고리즘)

Knapsack 알고리즘:

Knapsack 알고리즘이란 n개의 물건을 배낭에 최대 가치로 넣는 문제이다.

• 배낭에는 무게 수용치가 정해져있다. (ex: 15kg)
• n개의 물건은 각각 다른 가치와 다른 무게가 정해져있다.

위 문제는 물건을 쪼갤 수 있는 경우와 아닌 경우로 나뉜다. (Fraction Knaspack Problem & 0-1 knapSack Problem)

---

0-1 knapSack Problem(쪼갤 수 없는 배낭문제):

위 문제는 대표적인 DP 알고리즘 문제이다. (동적계획법)

DP 알고리즘이란 큰 하나의 문제를 작은 여러개의 문제로 쪼개어 순차적으로 풀어나가는 방식이다.

 

위와 같은 경우를 보자.

• 배낭: 최대 15kg
• 물건: ($4, 12kg), ($2, 1kg), ($10, 4kg), ($2, 2kg), ($1, 1kg) 

위 경우에서 물건은 넣거나 넣지않거나로 이분적으로 생각할 수 있다.

무슨 물건을 먼저 넣느냐에 따라 이후에 넣을 수 있는 물건의 수와 종류가 변하게 된다.

만약 수용가능한 무게를 전부 채웠을거나, 넣으려고 하는 물건이 수용량을 초과한다면 넣을 수 있는 물건은 없다.

여기에서 하나의 수식을 만들 수 있다.

• B[][]: 최대 가치를 담는 배열이다.
• k: 현재 넣은 물건의 번호이다.
• W: 넣을 수 있는 최대 무게이다.
• Wk는 k번째 물건의 무게이다.

즉 위 수식은 k번째 물건이 W(수용가능한 무게)를 초과할 경우,

최대 가치는 k-1번째 물건을 넣은 순간인 B[k-1][W]이라는 것이다.

 

하지만 이것이 최대 가치임을 뜻하는 것은 아니다.

넣는 순서에 배낭에 들어가는 물건은 달라지고 가치 역시 달라질 수 있기 때문이다.

(k번째 물건을 넣기 위해 k-1번째 물건을 빼내고 다시 k번째 물건을 넣는 경우를 생각해보자)

만약 k-1을 빼내고 K를 넣었을 때의 가치가 전자보다 커진다면 우리는 그것을 선택해야 한다.

따라서 우리는 위와 같이 두 경우에 대해 max()연산을 하여 더 가치가 높은 경우를 택한다.

---

표로 이를 생각해볼 수 있다. 이때 물건은 무게순으로 정렬한다.

• 배낭: 최대 6kg
• 물건: 1($2, 1kg), 2($3, 2kg), 3($1, 3kg), 4($4, 4kg), 5($10, 5kg)

최대무게\물건번호	1($2, 1kg)	2($3, 2kg)	3($1, 3kg)	4($4, 4kg)	5($10, 5kg)
0kg	$0	$0	$0	$0	$0
1kg	$2
2kg	$2
3kg	$2
4kg	$2
5kg	$2
6kg	$2

*물건을 담는 경우에는 해당 물건의 가치를 테이블에 명시한다.

1. 담을 수 있는 최대 무게가 0일 때는 아무런 물건을 담을 수 없다. 따라서 첫 행은 전부 0이다.

2. 첫번째 물건은 1kg이다. 즉 1kg이상 담을 수 있는 경우엔 전부 넣을 수 있다.

 

최대무게\물건번호	1($2, 1kg)	2($3, 2kg)	3($1, 3kg)	4($4, 4kg)	5($10, 5kg)
0kg	$0	$0	$0	$0	$0
1kg	$2(1)	$2(1)
2kg	$2(1)	$3(max(1,2) = 2)
3kg	$2(1)	$5(1,2)
4kg	$2(1)	$5(1,2)
5kg	$2(1)	$5(1,2)
6kg	$2(1)	$5(1,2)

3. 2번째 물건($3, 2kg)을 고려한다. 1kg일 때는 넣을 수 없으니 1번 물건을 넣는것이 최대 가치이다.

4. 2kg인 경우에는 1번 물건을 빼고 2번 물건을 넣을 수 있다. max(1,2)를 하면 2번을 넣는 것이 가치가 크다.

5. 3kg 이상부터는 둘 다 넣을 수 있다.

*위 작업을 물건 5까지 진행해보자.

최대무게\물건번호	1($2, 1kg)	2($3, 2kg)	3($1, 3kg)	4($4, 4kg)	5($10, 5kg)
0kg	$0	$0	$0	$0	$0
1kg	$2(1)	$2(1)	$2(1)	$2(1)	$2(1)
2kg	$2(1)	$3(max(1,2))	$3(max(1,2))	$3(max(1,2))	$3(max(1,2))
3kg	$2(1)	$5(1,2)	$5(1+max((2),3))	$5(1+max((2),3))	$5(max((1,2),3))
4kg	$2(1)	$5(1,2)	$5(1+max(2,3))	$5(1,2)  max((1,2),4)	$5(1,2)  max((1,2),4)
5kg	$2(1)	$5(1,2)	$5(1+max(2,3))	$6(1,4)	$10(5)
6kg	$2(1)	$5(1,2)	$6(1,2,3)	$7(2,4)	$12(1,5)

*5kg 4번부터 헷갈린다. 따라서 거기부터 보겠다.

6. 5kg부분에선 물건 1,2가 들어있고 3kg을 차지하고 있다. 즉 2kg의 여분이 있다.

7. 물건 1를 빼면 3kg의 여분이 남고 물건 3을 넣을 수 있다. 따라서 위 수식으로 값을 얻는다. 2+max(1,3)=$5

8. 물건 2를 빼면 4kg의 여분이 남고 물건 4을 넣을 수 있다. 따라서 위 수식으로 값을 얻는다. 1+max(2,4)=$6

9. 7번 8번의 값으로 다시 max()연산을 하면 물건 1,4를 넣는 것이 최대 가치를 충족함을 알 수 있다. 

*그 뒤부턴 쉽다~

 

pseudo code

for w = 0 to W
    B[0][W] = 0
for i = 1 to n
    B[i][0] = 0
    for w = 1 to W
    if w[i] <= w
        if b[i] + B[i-1][w-w[i]] > B[i-1][w]
            B[i][w] = b[i] + B[i-1][w-w[i]]
        else B[i][w] = B[i-1][w]
    else
        B[i][w] = B[i-1][w]

직접 구현해보자!