10. Backtracking ㅣ Knapsack 문제

Backtracking ?

 기존에 알아보았던 Divide＆conquer, Dynamic programming 그리고 나중에 알아볼 Greedy 등의 알고리즘은 문제를 효율적으로 풀기 위해 사용했지만, Backtracking은 효율성보단 정확성에 조금 더 초점에 둔 알고리즘이다.

---

Knapsack 문제 ?

여러 물건의 무게와 가격이 주어지고, 배낭에 담을 수 있는 총 용량(크기 또는 무게) 제한 K가 있다면, 배낭 용량 제한 K를 넘지않도록 물건을 골라 배낭에 담는 문제

☆ 목표 ❗ :선택한 물건의 가격(이익)의 합이 최대가 되도록 선택

---

Knapsack 문제의 여러가지 버전

1. fractional knapsack 문제 

선택한 물건의 일부분을 배낭에 넣을 수 있는 문제.

 

가루처럼, 물건을 나눠 담을 수 있다는 조건이 중요하다.

 

❓❔ 그러면 어떤 기준으로 물건을 선택하는게 좋을까 ❔❓

단위 용량당 가격이 가장 높은 물건을 선택해 최대한 가성비 좋게 배낭에 담으면 어떨까 ?

가격 = [40, 30, 50, 10], 용량 = [2, 5, 10, 5]일때,

단위 용량당 가격을 나열하면 (40/2, 30/5, 50/10, 10/5) → (20, 6, 5, 2)로 이미 단위 용량당 가격이 가장 높은 물건 순으로 나열되어있다.

이처럼, 단위 용량당 가격을 구해 큰 순서대로 가방에 담으면 된다.

 

이 선택 기준은 Greedy 알고리즘의 정의에 의해 항상 답을 보장한다.

 

2. 0/1 knapsack 문제

선택한 물건을 나눠 배낭에 넣을 수 없고 전체를 넣어야 하는 문제.

길이가 n(물건 개수)인 리스트 X가 있을때, 물건 순대로 1이면 선택, 0이면 선택 x 

ex) X = [1,0,0,1] 일때, 가격 40과 가격 10인 물건을 고른 것.

➡ 전체 경우는 2ⁿ임을 알수있다.

 

위 fractional knapsack 문제 처럼 물건을 나눠 담을 수 없다.

 

0/1 knapsack 문제는 위에 사용한 Greedy 선택기준으로 물건을 담으면 항상 답을 보장하지 않는다.

 

고로 Backtracking을 통해 모두 탐색해 답을 찾아야 한다 ...

물론 Boundry조건을 잘 작성하면 효율적이게 답을 구할 수 있다 !

---

★fractional knapsack 문제 >= 0/1 knapsack 문제★

  0/1 knapsack 문제로 선택한 정답은 fractional knapsack 문제로도 모든 걸 선택할 수 있지만,

fractional knapsack 문제로 선택한 정답은 0/1 knapsack 문제로 모든 걸 선택 할 수 없기 때문에,

모든 fractional knapsack 문제의 정답은, 모든 0/1 knapsack 문제의 정답을 포함하고 있다.

 

이는 Backtracking중 Boundry조건을 설정할때 쓰이는 중요한 사실이다.

 

★Boundry조건 ?

 물건을 i까지 선택했을때, 가장 좋은 선택에 대한 가격의 합을 MP라 하자.

다음 물건을 담기위해 물건을 탐색한다고 할때, 물건 i +1, …, n에 대해, 배낭의 남은 용량을 넘기지 않으면서 추가로 선택할 수 있는 최대 예상 이익은 fractional knapsack 방법을 통해 얻은 가격의 합으로 정할 수 있다.

이때 최대 예상 이익이 MP보다 작다고 하면, 더 이상 탐색할 필요가 있을까 ? 없다.

우리의 목적은 최대 예상 이익을 구하는 것인데, 다음 탐색이 이뤄질때 더이상 MP보다 큰 이익을 얻을 수 없기 때문이다.

 

★즉 ! 예상 이익이 MP보다 큰 경우에만 탐색하면 된다!

 

---

상태 공간 트리로 알아보기

 p(가격) = [15, 16, 6], s(용량) = [3, 4, 2], K = 5

가성비 = (5, 4, 3) 일때,

p(v) = 노드 v에서 현재 선택한 물건의 가격의 합 (이익의 합)
s(v) = 노드 v에서 현재 선택한 물건의 용량의 합
MP = 현재까지 가장 좋은 선택에 대한 가격의 합

↓

↓

↓

↓

---

[출처]

신찬수 교수 (한국외국어대학교 컴퓨터 공학부), ‘알고리즘 - Algorithm with Python’, p.112~115

-Youtube : ‘Chan-Su Shin’

Chan-Su Shin