[swjungle 2기] 도둑! 배낭? Knapsack Problem(배낭문제, 냅색)

Knapsack (배낭 문제)

• Knapsack(배낭) 문제는 DP의 대표적인 문제 유형중 하나입니다.
• 배낭이 있고 배낭에 담을 수 있는 최대 무게가 주어집니다. 배낭에 담을 수 있는 물품들도 주어지는데, 각각 무게와 benefit(가치)가 다릅니다. 이 문제의 목표는 **배낭에 담을 수 있을 만큼 물품들을 넣었을 때 benefit(가치)가 최대가 되는 짐을 고르는 것입니다. 단, 물품들을 쪼갤 수 없다고 가정합니다. 쪼갤수 없다고 가정한 문제를 0-1 knapsack problem이라고 부릅니다.
• 물품들을 쪼갤 수 있다고 가정해서 푸는 knapsack 문제는 fractional knapsack problem이라고 부릅니다.
• 예제
  • 배낭의 최대 무게는 5
  • (무게, 가치) 형태의 물품 4개
    1. (2, 3)
    2. (3, 4)
    3. (4, 5)
    4. (5, 6)
• 배낭의 최대 무게를 넘지 않는 선에서 최대 가치를 줄 수 있는 물품들을 적절히 선택해야 합니다. DP를 사용하면 문제를 sub-problem들로 나누고 그 안에서 각 sub-problem들에 대한 최적의 답을 저장해야 합니다.
• 값들을 저장하기 위해 일반적으로 2D Array를 만들어서 문제를 풉니다. W는 배낭의 최대 무게이고 N은 물품의 index입니다. W[2], n[2]는 담을 수 있는 무게가 총 2이고, 1번과 2번 물품들 중에서만 고르겠다는 의미입니다. 초기에 최대 무게가 0이던지, 고를 수 있는 물품이 0개이면 아무 가치도 얻을 수 없기 때문에 0으로 행렬을 초기화 합니다.

  W\N	0	1	2	3	4
  0	0	0	0	0	0
  1	0
  2	0
  3	0
  4	0
  5	0

• 이제 2D Array를 하나씩 채우면서 배낭 무게 5일때 최대 가치를 구하려고 합니다. W[5], N[4]에 오는 값이 답이 될 것입니다. 이 Array를 풀어나가려면 아래의 조건을 따라가면 됩니다.

            1. knap[i-1, W] --> if w_i > W
knap[i W] =
            2. max(knap[i-1, W], knap[i-1, W-w_i] + b_i) --> else

• 위에 식은, 내가 넣을 수 있는 물품이 있는데, 그 물품을 배낭에 넣었을 때 최대 무게를 초과한다면 benefit(가치)를 그대로 가져오겠다는 것입니다. 밑의 식은, 새로운 물품이 있고 최대 무게를 넘어서지 않는다는 것 입니다. 이제 이전 benefit(가치)와 이전 것의 물품을 빼고 내가 새로 받은 물품의 가치를 넣었을 때의 가치를 비교해서 더 큰 것을 취합니다.
• W[1], N[1]일 때, (2, 3)인 물품을 넣을 수 있게 됩니다. 나에게 주어진 최대 무게는 1이지만, 가지고 있는 물품의 무게는 2이기 때문에 해당 물품을 넣을 수 없게 됩니다. 그렇기 때문에 이전 benefit(가치)를 그대로 가져와서 0이 되는 것입니다.

  W\N	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\N	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\N	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\N	0	1	2	3	4
  0	0	0	0	0	0
  1	0	0	3	3	3
  2	0	3	4	4	4
  3	0	3	4	5	5
  4	0	3	4	5	5
  5	0	3	4	5	7

 

0-1 Knapsack 문제, Python풀이

N, W = 4, 5
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)

1-D array로 0-1 knapsack 문제 풀기

• 위에서는 2D array로 배낭 문제를 해결했지만, 사실 이 문제를 1D array로도 풀 수 있습닏다. 2D array로 문제를 풀면 각 칸이 무엇을 의미하는지 보다 직관적으로 알 수 있지만, N과 W의 크기가 커지면 메모리도 많이 차지하게 되는 단점이 있습니다. 1D array로 문제를 풀면 (2D-array 크기)/ N 만큼의 메모리만 사용하면 됩니다.

N, W = 4, 5
bag = [(2,3), (3,4), (4,5), (5,6)] # (weight,benefit) 순서

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

for i in range(N):
    for j in range(W, 1, -1):
        if bag[i][0] <= j:
            knap[j] = max(knap[j], knap[j-bag[i][0]] + bag[i][1])

print(knap)

• 위의 알고리즘을 실행시키면 아래처럼 실행이 됩니다.
  • i = 0, j = 5
    • bag[i][0]은 2이고 5보다 작기 때문에 if 구문이 실행됩니다. knap[j]는 0이고 knap[j - bag[i][0]]도 0이고 bag[i][1]은 3입니다. max 함수에 의해서 knap[j - bag[i][0]] + bag[i][1]의 값이 knap[j]에 저장이 되는 것 입니다.
  • i = 0, j = 4
    • 위와 같은 조건으로 if 구문이 실행됩니다. knap[j]는 0이고 knap[j - bag[i][0]]도 0이고, bag[i][1]는 3이기 때문에 더 큰 값을 저장하는 것 입니다.
  • ...
  • i = 1, j = 5
    • 그림에서 5 번째 줄에 해당하는 내용입니다. bag[i][0]는 3이고 j보다 작기에 if 구문이 실행됩니다. knap[j]는 3이고, knap[j-bag[i][0]]도 3이고 bag[i][1]은 4이다. 3 < 3+ 4 이기 때문에 7이 저장이 됩니다.
  • ...

  1. [ 0, 0, 0, 0, 3 ]
  2. [ 0, 0, 0, 3, 3 ]
  3. [ 0, 0, 3, 3, 3 ]
  4. [ 0, 3, 3, 3, 3 ]
  5. [ 0, 3, 3, 3, 7 ]
  6. [ 0, 3, 3, 4, 7 ]

• knap[j-bag[i][0]]이 무슨 일을 하는지 알면 이해하는 것이 더 쉬워진다. 기존의 index에서 새로 들어온 물품의 무게를 빼는 것이다. 그렇게 해서 나온 index는 새로 들어온 물품과 함께 선택할 수 있는 물품의 무게가 되는 것이다. 그렇다는 것은 해당 index의 값은 기존 물품의 benefit(가치)이고 그 값에 새로운 물품의benefit(가치)를 더하면 새로운 benefit(가치)를 구할 수 있게 되는 것이다.

Knapsack - fractional (Greedy)

• 지금까지는 물품들을 쪼갤 수 없다고 가정했기 때문에 DP를 사용해서만 문제를 풀 수 있었습니다. 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)

---

출처 : https://dojinkimm.github.io/algorithm/2019/10/19/dp-2.html
본인 : https://github.com/kqjatjr/JUNGLE/blob/main/WEEK04/0827.md