Knapsack Problem(배낭 문제)란, 도둑이 배낭에 담을 수 있는 물건의 무게에 한계가 있는 상황에서 각 물건의 가치가 다를 때, 물건의 가치를 최대로 만드는 문제로, Fractional과 0-1의 두 가지 방식이 있다.
Fractional Knapsack Problem은 같은 상황에 대해 물건을 일정 비율만큼 훔칠 수 있는 경우로, 물건을 분할해서 가져갈 수 있는 문제이고,
0-1 Knapsack Problem은 하나의 물건에 대해 나눌 수 없고, 훔치거나 훔치지 않는 선택만을 할 수 있는 경우의 문제이다.
Fractional Knapsack Problem은 각 물건을 원하는대로 가져갈 수 있기 때문에 단위 무게당 가치(가치/무게)를 구해서 그 값이 높은 순서대로 배낭을 채운다.
그래서 물건을 선택할 때에 그리디 알고리즘을 이용하여 결과를 구한다.
예제 테이블에서, 물건 1, 2, 3의 Value Density는 각각 6, 5, 4이다. 따라서, 물건을 선택할 떄 물건 1, 2, 3의 순서로 선택하면 된다.
[그리디 알고리즘에 대한 자세한 내용은 아래 링크 참고]
[알고리즘] 그리디 알고리즘 / Greedy Algorithm
그리디 알고리즘은 현재 가장 좋아보이는 선택을 하는 알고리즘이다. 다시 말해, 순간마다 최적의 선택을 진행하여 적합한 해를 도출하며, 그것이 전체의 최적이 될 것이라고 생각한다. 문제의
9-coding.tistory.com
W = 50, 최대로 가져갈 수 있는 무게가 50일 때의 위 테이블을 참조하여 최대 가치를 구해보자.
위에서 구한 단위 무게 당 가치가 가장 높은 순서대로 선택해주면 되는데,
이때 최대 무게가 50인 상황에서 최대 가치여야 한다는 것은 무게가 정해진 상황에서 최대 가치를 만들어야 하기 때문에 결과 역시도 단위 무게 당 가치가 높아야 한다.
각각의 부분이 최적의 효율일 때 전체도 최적일 수 있으므로, 부분 최적이 전체 최적이 되기 때문에 0-1 Knapsack Problem은 그리디 알고리즘 방식으로 해결이 가능하다.
이렇게 최적인 물건들을 선택하다 남은 무게 보다 넣을 물건의 무게가 높을 때, 해당 물건을 남은 크기만큼 잘라서 넣어주면, 가장 높은 가치를 만들어낼 수 있다.
(예제에서는 20만큼 남은 무게에 30을 넣고자 할 때, 해당 물건을 20만큼 쪼개서 넣은 것을 볼 수 있다)
위에서 설명한 내용을 종합한 내용.
0-1(Zero-one) Knapsack Problem은 물건을 쪼갤 수 없는 상황에서 물건을 포함(1)하거나 미포함(0)하여 최대 가치를 구하는 문제이다.
Fractional Knapsack Problem에서 들었던 예시와 같은 테이블로 0-1 배낭 문제를 설명하면,
그리디 알고리즘을 사용했을 때는 일단 단위 무게 당 가치, 즉 효율이 가장 좋은 선택을 차례로 하므로 아이템 1과 2를 선택하고, 무게 제한으로 인해 3은 선택할 수 없다. 이때, 가치는 160이고, 무게는 30이다.
그런데, 실제 최적해는 아이템 2와 3을 선택하는 경우로, 가치는 220이고, 무게는 50이다.
따라서 그리디 알고리즘으로는 0-1 배낭 문제를 해결할 수 없다는 결론에 도달한다.
이제 동적 계획법으로 0-1 배낭 문제를 해결해보자.
[동적 계획법에 대한 자세한 내용은 아래 링크 참고]
[알고리즘] Dynamic Programming (동적 계획법)
동적 계획법, Dynamic Programming(DP)는 최적화 이론의 한 종류로, 특정 값을 구하기 위해서 다른 범위의 값을 이용해 효율적으로 값을 구하는 알고리즘으로, 쉽게 말해 답을 재활용하는 알고리즘이다
9-coding.tistory.com
dp[i][j] 테이블은 i번쨰 물건까지 보았을 때 j는 최대 수용 무게이고, 해당 dp테이블의 값은 현재의 최대 가치를 나타내고,
w[i]는 무게, v[j]는 가치를 나타낸다고 했을 때ㅡ
j < w[i]인 상황에서 dp[i-1][j],
j >= w[i]인 상황에서는 dp[i-1][j]과 dp[i-1][j -w[i]]+v[i] 중에서 큰 값을 택해 dp[i][j]에 저장한다.
즉, 이전의 최댓값과 이전 물건에서 현재 물건 무게를 뺀 값과 현재 가치의 합을 비교해서 큰 값을 저장한다는 의미이다.
이제, 직접 테이블을 작성해보자.
예제에서 i는 물건의 개수이므로 0, 1, 2, 3으로 설정해주었고, 물건들의 무게와 제한 무게가 모두 10의 배수이므로, 임의로 간단하게 j를 10의 배수 꼴로 설정하였다.
첫번째 행과 열은 0으로 모두 초기화해주고 테이블 채우기를 시작한다.
테이블을 전부 채우면 이와 같은 모습이 되고, 정답은 많은 dp 문제들이 그러하듯 정답은 맨 오른쪽 아래에 있고, 위에서 봤던 최적해의 값과 일치하는 것을 볼 수 있다.
이 dp테이블에서 중요한 포인트들을 추려 직접 적어보았다.
dp 문제를 이해할 때, 잘 이해가 되지 않는다면, 이렇게 직접 식에 값을 대입해 값을 비교하며 테이블을 채우다 보면 잘 이해할 수 있다.
테이블을 확인해보면, 물건 1, 2를 선택하여 가치 220을 만들어냈음을 파악할 수 있다.
'알고리즘' 카테고리의 다른 글
| [알고리즘] Prim's Algorithm (필기자료) (1) | 2023.10.18 |
|---|---|
| [알고리즘] Graphs (필기자료) (0) | 2023.10.18 |
| [알고리즘] 마스터 정리 The Master Method (0) | 2022.10.19 |
| [알고리즘] 재귀 트리 Recursion Tree (0) | 2022.10.17 |
| [알고리즘] 점근 표기법 Asymptotic Notations (Big-O, Omega, Theta, Little-o, Little omega) (0) | 2022.10.01 |