냅색 알고리즘 (Knapsack Algorithm)개념과 원리

[ 목차 ]

1. 개요

2. 냅색 알고리즘 개념

3. 냅색 알고리즘 원리

개요

특정 가중치와 할당된 값을 가진 항목 집합이 주어지면 가중치 제약 내에 머무르면서 배낭의 값을 최대화하는 것이 목표인 시나리오에서 유래된 알고리즘 입니다.

냅색 알고리즘은 optimization 카테고리에 속하는 DP(Dynamic Programming) 문제 입니다.

*optimization

DP(Dynamic Programming) 해법으로는 총 두가지가 있습니다.

1. Overlapping subproblem

2. Optimal substructure

여기서 냅색 알고리즘은 2번째 Optimal substructure은 작은 문제의 최적 해법으로 원래 문제의 최적 해법을 구하는 방식 입니다.

 

문제 예시를 들어보면,

마리는 배낭과 4개의 과일을 가지고 있습니다. 배낭에 과일을 넣고 다니며 수익을 극대화 하고 싶습니다. 그러기 위해선 어떤 과일을 몇개씩 담아야 수익을 극대화 할 수 있을 까요?

(제한사항 : 배낭의 가중치보다 크면 안됩니다.)

 

INPUT

Items	{Apple, Orange, Banana, Grape}
Weights	{2,3,1,4}
Profits	{4,5,3,7}
Knapsack Capacity	5

 

마리가 가장 큰 수익을 냈을 경우

: Banana(1) + Grape(1) = 3+7 =10

 

문제 접근 방식

문제 접근 방식에는 총 3가지 방식이 있습니다.

 

- brute-force

- top-down with memozation

- bottom-up

 

이중 두 가지 접근법(top-down with memozation, bottom-up)은 동적 프로그래밍을 사용합니다.

더 복잡한 상황에서, 이 두가지 방법은 훨씬 더 효율적인 사용 접근법이 될 것 입니다.

 

원리

(1) 모든 과일을 일일히 방문해 확인하는 방법 (brute-force)

brute-force 방식대로 일일히 하나씩 확인합니다.

사과, 오렌지, 바나나, 포도 하나씩 무조건 들어가 있으면서 무게의 가중치 5를 넘기지 않은 이익들을 모두 구합니다.

 

- 사과🍎가 무조건 들어가 있을 경우

사과(1) + 오렌지(1) = 4 + 5 = 9

사과(1) + 바나나(1) = 4 + 3 = 7

 

- 오렌지🍊가 무조건 들어가 있을 경우

오렌지(1) + 바나나(1) = 5 + 3 = 8

 

- 바나나🍌가 무조건 들어가 있을 경우

바나나가 무조건 들어가 있을 경우는 앞의 경우에서 모두 확인했기 때문에 확인하지 않는다.

 

- 포도🍇가 무조건 들어가 있을 경우

포도(1) + 바나나(1) = 7 + 3 = 10

 

구한 이익들 중 가장 높은 이익을 차지하는 건 포도,바나나가 하나씩 들어가있을때 가중치(10)가 제일 높습니다.

이처럼 brute-force방식은 모든 경우의 수를 확인하므로 최소 (On²) 시간이 걸립니다. 이는 DP문제에서 시간초과가 날 가능성이 높습니다.

 

(2) Top-down, Botton-up

 

위의 표에 초기 세팅을 해주었습니다.

i의 최대값은 과일의 총 개수(4) 입니다. w의 최대값은 가방의 가중치(5) 입니다.

우선 간단한 접근 방식은 배낭 크기가 1인 경우 최대값을 얻은 다음 배낭크기가 2인 경우 최대값을 계산하는 방법입니다.

 

1. 첫 번째 행과 열 0으로 초기화

그림에서 보면 첫 번째 행과 첫 번째 열은 항상 0으로 초기화 해줍니다. 왜냐하면 항목이 없으면 어떤 값도 얻을 수 없기 때문입니다. 배낭 크기가 0일 경우 어떤 물건도 배낭에 넣을 수 없습니다.

 

 

2. 과일별로 각 무게 당 이익을 확인 최대 무게는 배낭의 크기

사과 -> 오렌지 -> 바나나 -> 포도 순으로 무게가 증가할수록 최대 수익을 낼 경우를 조사합니다.

 

🍎사과

 (1) 사과 한개로 1키로 무게에 대한 수익

사과의 무게는 2kg이기 때문에 1키로 일 경우 수익을 낼 수 없어 0이 됩니다.

 

(2) 사과 한개로 2키로 무게에 대한 수익

사과의 무게는 2kg이기 때문에 2키로 일 경우 4의 수익을 낼 수 있습니다. 

 

(3) 사과 한개로 3~5 키로 무게에 대한 수익

무게가 3~5kg 일때도 같습니다. 사과는 한개밖에 없기때문에 모두 최대수익을 4를 낼 수 있습니다.

 

🍊 오렌지

오렌지부터는 최대 수익을 내는 방법이 다르게 확인해야됩니다.

 

(1) 오렌지 한개가 있을 때 1키로 무게에 대한 최대 수익

오렌지의 무게는 3kg입니다. 그러므로 1키로 무게에 대한 수익을 낼 수 없습니다. 그러므로 기존에 사과로 1키로 수익을 냈을 경우를 확인합니다. 똑같이 수익을 내지 못했기 때문에 1키로 무게에 대한 수익은 0입니다.

 

(2) 오렌지가 한개가 있을 때 2키로 무게에 대한 최대 수익

2키로 일때도 마찬가지로 오렌지의 무게는 3kg이기 때문에 수익은 0 입니다. 반면 사과로 2키로의 수익을 냈을 경우를 확인해보면 사과는 

4의 수익을 냈습니다. 이 결과로 사과, 오렌지를 활용해 2kg의 무게에서 4의 수익을 낼 수 있다는 것을 알 수 있습니다. 그럼 오렌지 한개가 있을 때 2키로 무게에 대한 최대 수익은 4가 되므로 4를 넣어 줍니다.

 

(3) 오렌지가 한개 있을 때 3키로 무게에 대한 최대 수익

3kg일 때는 상황이 달라집니다. 오렌지가 3kg이기 때문에 배낭에 넣을 수 있고 이에 대한 최대수익은 5가 됩니다. 반면 사과 한개가 있을 때의 최대수익은 4이기 때문에 오렌지를 넣었을 때 수익이 가장 크므로 5를 넣어줍니다.

 

(4) 오렌지가 한 개 있을 때 4키로 무게에 대한 최대 수익

4키로일 때도 같은 상황인데 확인해야 될 것이 있습니다. 우선 4키로 배낭에 3키로에 오렌지를 넣을 수 있습니다. 그러면 배낭은 1kg의 

여유 무게가 생깁니다. 이때 사과가 1kg 무게에서 나온 최대 수익을 더해줍니다. 하지만 사과의 1kg무게에서 나온 최대 수익은 0이므로

5를 넣어줍니다.

 

(5) 오렌지가 한 개 있을때 5키로 무게에 대한 최대 수익

 

무게가 5키로 일대 오렌지 한개를 넣을 수 있습니다. 이때 2키로의 여유 무게가 생깁니다. 우리는 가방에 과일을 넣어 최대 수익을 내는 것이

목표이므로 가방에 무게가 찰때까지 과일을 넣어서 수익을 내야됩니다. 그럼 여기서 오렌지를 넣었으니 사과를 이용해 2키로의 무게에 낼 수 있는 수익을 확인해줍니다. 

 

2kg의 무게에서 사과로 만들어낸 최대 수익은 4입니다. 그럼 여기서 오렌지 수익 + 사과의 수익 과 5kg의 무게에서 사과의 최대이익을 비교해줍니다. 

오렌지 수익 + 사과의 수익 = 9

 5kg의 무게에서 사과의 최대이익 = 4

위의 수익이 가장 큰 수익을 내므로 9를 갱신해줍니다.

 

3. 모든 과일로 최대 이익을 내는 경우를 확인

위의 표는 모든 과일을 넣으면서 과일의 갯수별로 최대 수익을 확인한 결과 입니다. 최종적으로 무게가 5kg일 때, 포도까지

넣으며 확인 한 수익 (4,5)의 위치에 있는 값이 우리가 알아낸 최대 수익이 됩니다.

우리가 과일과 무게를 확인하며 최대이익을 구한 방법은 위의 공식처럼 표현 할 수 있습니다.

위의 공식을 예제로 보여드리면,

오렌지로 5키로의 무게에서 최대 수익 = MAX(사과 한개의 최대수익, 오렌지 한개의 수익 + 2키로의 무게에서 사과 한개로 낸 최대 수익)

이런식으로 공식을 유추해낼수 있었습니다.

 

 

지금까지 과일과 무게를 예시로 들며, 냅색알고리즘의 원리와 공식을 도출해보았습니다.

다음 포스팅에서는 실제 문제와 풀이 방식에 대해서 설명해보겠습니다.

감사합니다.

 

 

참고 사이트

- https://www.educative.io/answers/what-is-the-knapsack-problem

What is the Knapsack Problem?