0/1 KnapSack ✔

배낭 문제(KnapSack Algo) ❗

• 배낭 문제란 배낭에 담을 수 있는 최대 허용 무게값이 정해져 있고, 일정한 가치와 무게가 정해져있는 짐들을 배낭에 담을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

---

1️⃣ 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)

• 물건을 쪼갤 수 없는 배낭문제의 경우는 동적계획법을 활용해 해결

2️⃣ 물건을 쪼갤 수 있는 배낭문제(Fracktion Knapsack Problem)

• 물건을 쪼갤 수 있는 배낭문제의 경우는 가치가 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식으로 그리디 알고리즘으로 해결 가능

---

0/1 Knapsack Problem 동작과정 🔽

0/1 Knapsack Problem 문제를 해결하기 위해서는 동적 계획법을 이용

가방에 담을 수 있는 물건의 무게와 가치가 아래 표와 같을 때,

물건	1	2	3	4
무게	2	3	4	5
가치	3	4	5	6

이때, 행 i는 가방의 최대 무게를 의미 행 j는 물건 j까지 넣을 수 있을 때를 의미, 열 j는 가방의 최대 무게를 의미

[초기 상태]

• 초기에 최대 무게가 0이 던지, 내가 고를 수 있는 물품이 0개이면 아무 benefit(가치)도 얻을 수 없기 때문에 다 0으로 행과 열을 초기화 한다.

W/I	0	1	2	3	4
0	0	0	0	0	0
1	0
2	0
3	0
4	0
5	0

❗ 점화식

if w_i > W
  Knap[i, W] = Knap[i-1, W]

else
  Knap[i, W] = max(Knap[i-1, W], Knap[i-1, W - w_i] + b_i)

• 위에 식은, 내가 넣을 수 있는 물품이 있는데, 그 물품을 배낭에 넣었을 때 최대 무게를 초과한다면 benefit(가치)를 추가하지 않고 이전 benefit(가치)를 그대로 가져오겠다는 것이다. 밑에 식은, 나에게 새로운 물품이 있고 최대 무게를 넘어서지 않는다는 것이다. 이제 이전 benefit(가치)와 이전 것의 물품을 빼고 내가 새로 받은 물품의 가치를 넣었을 때의 가치를 비교해서 더 큰 것을 취한다.

[W-1, N-1]

• (2, 3)인 물건을 넣을 수 있게 된다.
• 나에게 주어진 최대 무게는 1이지만, 내가 가지고 있는 물품의 무게는 2이기 떄문에 해당 물품을 넣을 수 없게 된다. 그렇기 때문에 이전 benefit(가치)를 그대로 가져와서 0이 되는 것이다.

W/I	0	1	2	3	4
0	0	0	0	0	0
1	0	0
2	0
3	0
4	0
5	0

[W-2, N-1]

• 나에게 있는 (2,3) 물품을 넣을 수 있게 되기 때문에 물품을 넣고 3이라는 benefit(가치)를 얻게 된다.

W/I	0	1	2	3	4
0	0	0	0	0	0
1	0	0
2	0	3
3	0
4	0
5	0

[ 이후 ]

• W가 늘어도 N-1로 고정되어있을 때 그 밑의 값들은 변하지 않고 3의 benefit(가치)를 갖게 된다. 이는 나에게 새로운 물품이 주어지지 않고 최대 허용가능한 무게만 늘었기 때문이다. 최대로 넣을 수 있는 물품의 무게가 늘어도 새로운 물품이 없으면 benefit(가치)를 향상시킬 수 없다.

W/I	0	1	2	3	4
0	0	0	0	0	0
1	0	0
2	0	3
3	0	3
4	0	3
5	0	3

이러한 조건을 따라서 2D array를 채우다보면 밑과 같은 결과를 얻게 된다. W-4, N-4일 때 (2,3), (3,4), (4,5), (5,6) 물품들을 가지고 있고 무게 4에서 최대로 얻을 수 있는 benefit(가치)는 5이다. 하지만, W-5로 변할 때 (5,6)에서 benefit(가치)가 6이 되는 것이 아니라, (2,3), (3,4) 물품들을 선택해서 7의 benefit(가치)를 얻게 된다. knap[i-1, W-w_i] + b_i 가 더 크기 때문에 값이 바뀌게 된 것이다.

W/I	0	1	2	3	4
0	0	0	0	0	0
1	0	0
2	0	3	3	3	3
3	0	3	4	4	4
4	0	3	4	5	5
5	0	3	4	5	7

---

코드 🚀

N, W = 4, 5
# w_i당 b_i가 정렬되어잇어야함
w = [2, 3, 4, 5]
b = [3, 4, 5, 6]

knap = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N+1):
    for j in range(W+1):
      # 가방에 들어갈 수 있는 무게라면
        if w[i-1] <= j:
            knap[i][j] = max(b[i-1] + knap[i-1][j-w[i-1]],  knap[i-1][j])
        # 가방에 애초에 들어갈 수 없는 무게라면
        else:
            knap[i][j] = knap[i-1][j]

print(knap)

fracktional Knapsack Problem 동작과정 🔽

Fractional knapsack 문제는 물품들을 쪼갤 수 있다고 가정하기 때문에 Greedy 알고리즘으로 풀 수 있다. 기본 아이디어는 다음과 같다:

• benefit(가치) / weight(무게) 의 비율을 각 물품마다 구한다

• 비율이 높은 순으로 정렬을 한다

• 배낭에 물품들을 비율 높은 순으로 넣는다

  • 만약에, 물품의 무게가 무게 최대치보다 크다면
    • (물품의 비율) * (최대치까지 남은 무게)를 구해서 답에 더해준다
  • 아니라면
    • 물품을 그대로 배낭에 넣고, 배낭에 넣을 수 있는 최대치 무게 값 들어간 무게만큼 줄인다.

N, W = 4, 5
w = [2, 3, 4, 5]
b = [3, 4, 5, 6]
ratio = [[0, 0] for _ in range(N)] # 왼쪽은 ratio값, 오른쪽은 index를 저장한다

for i in range(N):
    ratio[i][0] = b[i]/w[i]
    ratio[i][1] = i

ans = 0
for r in sorted(ratio, key=lambda x:-x[0]):
    if w[r[1]] <= W:
        W -= w[r[1]]
        ans += b[r[1]]
    else:
        ans += (W * r[0])
        break
print(ans)