Knapsack Problem(DP)-알고리즘11
Knapsack Problem(배낭채우기 문제)
배낭채우기 문제는 최대용량 w를 가지는 배낭에 각각 다른 값어치,무게를 가지는 물건들을 넣을 때, 총 값어치(배낭에 넣은 물건들의 값어치의 합)가 최대가 되도록 물건들을 골라서 넣는 경우를 찾는 문제이다.
배낭에 책을 담으려고 한다.
배낭의 최대 용량은 W이며, 이를 초과해서 책을 담으면 배낭이 찢어질 것이다.각 책의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 책을 담는 방법은?
knapsack problem 에는 두가지 버전이 있다.
- 0-1 Knapsack problem :배낭에 물건을 담거나, 안담거나. -Dynamic Programming 을 사용한다.
- Fractional Knapsack Problem: 배낭에 물건을 쪼개서 담거나, 안담거나.-Greedy Algorithm을 사용한다.
0-1 Knapsack Problem : Dynamic Programming
다음의 값이 주어진다:
- 최대 용량 W
- 담을 물건들로 이루어진 집합 S: n개의 물건들
- 각 물건 $i$ 는 무게 $w_{i}$ 와 값어치 $b_{i}$가 있다.
Problem: 총 값어치가 최대가 되도록 배낭에 물건들을 골라서 담는 방법은?
1. Brute Force:
S에 n개의 물건들이 있으므로 각 물건들은 배낭에 1)들어가거나 2)안 들어가는 총 2가지의 경우의 수를 가진다.
즉, 총 $2^{n}$개의 경우의 수가 있다.
이 모든 경우의 수를 따지는 브루트포스로 풀면 시간복잡도는 O($2^{n}$)이므로 너무 시간이 오래걸린다.
2. Dynamic Programming:
최적 부분 문제에 대한 2가지 접근법:
Subproblem - 1
- 무게 W의 가방을 최대 가치로 가득 채우려면 무게 W-1일때 최대 가치로 가득 채웠을 때의 가방에 하나가 더 들어갈 수 있는지 확인
기존에 있던 가방에서 하나의 물건을 빼고 다른 하나를 넣는 것으로 최대가치를 만들수 있기 때문에 이 접근법은 틀리다. 즉 무게 W일 때의 조합과 무게 W-1일때의 조합이 달라질 여지가 충분히 있는 것이다.
따라서 이러한 접근으로 부분문제를 정의하면 문제가 생긴다.
Subproblem - 2
집합 B를 n개의 물건들 중 최적으로 고른 부분 집합이라고 하자.
- 집합 B가 n번째 물건을 포함하고 있지 않다면, B는 n번째 물건을 뺀 나머지 n-1개의 물건들 중에서 최적으로 고른 부분집합과 같다.
- 집합 B가 n번째 물건을 포함하고 있다면, B에 속한 물건들의 총 가치는 n-1개의 물건들 중에서 최적으로 고른 가치의 합에다가 물건 n의 가치을 더한 것과 같다. (단, n번째 물건을 넣었을 때 배낭의 총 무게를 초과하지 말아야 한다.)
이를 점화식으로 풀어보면 다음과 같다.
B[k,w]는 k개의 물건이 있고 배낭의 총 무게가 w일때 최대 가치를 뜻한다.
만약 물건 k를 넣으려고 하는데 k의 무게, $w_{k}$가 배낭의 최대 한도 w 보다 크다면 넣을 수 없으므로 k-1개의 물건으로 구한 최적 부분 답을 그대로 가져온다.
만약 물건 k를 넣을 수 있다면, 물건 k를 넣기 위해 배낭을 $w_{k}$만큼 비우고 k를 넣은 것(k-1개의 물건으로 $w-w_{k}$만큼의 무게를 채웠을 때 제일 가치가 큰 경우 + 물건 k의 가치 $b_{k}$) 또는 물건을 넣지 않은 것( k-1개의 물건으로 구한 최적 부분 답) 을 비교해서 더 큰 것을 가져온다.
아래는 이를 구현한 코드다.
DP를 위한 2차원 리스트를 만든 다음, 0번째 행/열을 0으로 초기화하고 나머지는 위의 점화식을 그대로 옮기면 된다.
for w = 0 to W
B[0,w] = 0
for i = 0 to n
B[i,0] = 0
for w = 0 to W
if w_i <= w
if bi + 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] // w_i > w