[알고리즘] Knapsack Problem: Optimization Problem/Maximize Problem

Knapsack Problem

---

포스트 난이도: HOO_Middle

[Notice] 포스트 난이도에 대한 설명

---

 

# Knapsack Problem

Knapsack이란 배낭 또는 가방이라는 의미를 가진 단어이다.

그렇다면 Knapsack problem은 배낭 문제라는 뜻으로 해석되는데 여기에서 문제의 해결책을 유추할 수 있다.

실제로도 Knapsack problem을 한국에서는 배낭 문제라고 부른다.

이제부터 이 "배낭 문제"라는 것이 무엇을 나타내는 것이며, 알고리즘과 무슨 관련이 있는지 알아보도록 하자.

 

우리가 가방에 무언가를 담고 싶을 때 마음대로 담을 수가 없다.

예를 들어 학교를 가거나 직장을 갈때 가져가는 가방에 자동차를 넣고 다닐 수는 없다.

가방마다 넣을 수 있는 용량과 무게가 어느 정도 정해져 있다는 것은 일반적인 상식이다.

여기서 말하는 배낭 문제, 즉 Knapsack problem은 특정 가방이 존재한다고 가정했을 때 얼마만큼의 물건을 담을 수 있는지에 대해서 해결하는 문제이다.

<Figure 1.>

 

예를 들어 위와 같이 10kg의 물건을 담을 수 있는 가방 또는 박스가 있다고 가정해보자.

이 가방에는 정확히 10kg만을 담을 수가 있다.

그러면 10kg에 최대한 맞추어 물건을 담는 것이 핵심 포인트인 셈이다.

 

<Figure 2.>

 

 

하지만 가치가 서로 다른 물건을 선택할 수 있다면 조건은 바뀌게 된다.

1kg과 2kg의 서로 각기 다른 물건이 존재하지만, 물건에 대한 가치는 3 달러로 동일하다고 가정해보자.

그렇다면 어떻게 물건을 가져가는 것이 더 효율적인 것일까?

당연히 1kg 물건을 더 많이 담아서 가져가는 것이 효율적인 선택일 것이다.

반대로 무게는 동일하지만 물건당 가치가 다르다면, 당연히 가치가 높은 물건을 담는 것이 유리하다.

이것이 사실상 Knapsack problem을 푸는 모든 과정의 끝이다.

 

# Knapsack problem의 optimization과 maximize

Knapsack problem에서 문제를 푸는 것이 중요한 것이 아니라 어떤 과정을 거치며 어떤 특징을 가지고 있는지 파악하는 것이 중요하다.

Knapsack problem은 사실상 2가지의 문제를 동시에 해결하고 있는데, 바로 효율성과 극대화이다.

영어로 하면 이를 optimization Problem 과 Maximize Problem이라고 할 수 있다.

한마디로 Knapsack problem을 알고리즘으로 구현한다면 앞서 이야기한 optimization과 maximize를 동시에 해결할 수 있다.

따라서 우리는 Knapsack problem의 원리를 이해하고 이를 알고리즘 화하여 program에 적용하기 위해서 Knapsack problem를 배우는 것이다.

 

#Knapsack problem 푸는 방법

Knapsack problem을 푸는 과정에 대해서 살펴보도록 하자.

Knapsack problem을 쉽게 이해하고 풀기 위해서는 표를 사용하는 것이 좋다.

 

Maximize Weight

8

Item	Value	Weight
1	1	1
2	6	2
3	18	5
4	22	6
5	28	7

 

예를 들어, 위와 같은 조건이 제시된 Knapsack problem이 있다고 가정해보자.

이 문제를 해결하기 위해서는 첫번째 Row에는 weight를 입력하고 첫 번째 Column에는 Item으로 된 표를 만든다.

Item의 가치와 무게를 비교해서 최고의 결과값을 산출하는 것이 이 문제의 핵심이다.

문제에 대한 표를 만들어보면 아래와 같이 결과가 산출된다.

 

Weight/ Item	0	1	2	3	4	5	6	7	8
Empty	0	0	0	0	0	0	0	0	0
{1}	0	1	1	1	1	1	1	1	1
{1,2}	0	1	6	7	7	7	7	7	7
{1,2,3}	0	1	6	7	7	18	19	24	25
{1,2,3,4}	0	1	6	7	7	18	22	24	28
{1,2,3,4,5}	0	1	6	7	7	18	22	28	29

 

우선, 이 표에서 유심히 살펴봐야 하는 부분은 데이터 입력이 시작되는 기준에 있는 첫 번째 열과 행이다.

Row와 Column 부분이 모두 0인걸 알 수 있다.

간단히 생각해서 가방에 넣을 수 있는 무게가 0kg이라면 당연히 선택할 수 있는 물건의 종류가 많더라도 넣을 수가 없다.

따라서 첫번째 Column은 모두 0이 된다.

마찬가지로 첫번째 Row의 경우에는 가방의 무게는 변하고 있지만 담을 수 있는 물건이 없기 때문에 모두 0이 된다.

나머지는 조건표를 참고하여 최고의 결괏값이 나오도록 표를 완성해주면 끝이 난다.

여기서 중요한 포인트는 가방의 무게가 달라지고 선택할 수 있는 물건의 종류가 많아짐에 따라 결괏값이 앞선 결과가 달라진다는 것이다.

또한 이미 최적의 값을 구한 경우에는 앞선 결과값이 변화된 기준에도 최적의 값이기 때문에 변하지 않고 동일하다.

예를 들어 선택할 수 있는 물건이 {1}에서 {1,2,3,4,5}로 바뀌더라도 가방 1kg에 담을 수 있는 물건은 한 가지 종류밖에 없다.

한마디로 기존 데이터와 비교하여 이미 최적화가 된 경우에는 데이터의 변동이 없다는 것이다.

반면에 새로운 조건으로 더 좋은 결과가 산출될 수 있다면 결과값은 바뀐다는 걸 알 수 있다.

 

# Knapsack problem 공식

Knapsack problem의 공식은 아래와 같다.

V[i,w] = max {V {i-1, w], V [i-1, w-w [i]]+P [i]}

 

---

# In conclusion, 3줄 요약

1. Knapsack은 배낭을 의미한다.

2. Knapsack problem = optimization & maximize

3. V [i, w] = max {V {i-1, w], V [i-1, w-w [i]]+P [i]}

---