0-1 Knapsack 1D

0-1 Knapsack 문제에 대한 고찰

• 0-1 Knapsack 문제의 점화식은 다음과 같음
  • m[i, w] = max(m[i - 1, w], m[i - 1, w - w_i] + v_i)
  • i번째 행을 구하기 위해 i - 1번째 행을 사용
• 이를 구현하기 위해 2차원 배열을 사용하면 간단함
• 그러나 실제로 사용하는 것은 마지막 행 / 열의 원소이므로, 이전 행들의 정보는 사용 후 덮어씌워도 됨
• 이를 활용해 1차원 배열로 구현이 가능
• 공간복잡도가 O(W)가 될 뿐만 아니라, 시간 복잡도는 동일해도 실제 계산 시간은 감소됨

0-1 Knapsack 1차원 배열 구현 코드

dp[0] = 0

for cur_v, cur_w in zip(values, weights):
    for w in range(max_w, cur_w, -1):
        dp[w] = max(dp[w], dp[w - cur_w] + cur_v)

코드 설명

1. dp[w] 는 물건들의 무게의 합이 w 이하일 때 가치의 최댓값. m[i, w]가 dp[w]에 계속 업데이트 됨
2. 좌변의 dp[w]값은 m[i, w], 우변의 dp[w - cur_w], dp[w] 값은 각각 m[i - 1, w - cur_w], m[i - 1, w] 으로 기존 점화식과 동일
3. 바깥쪽 for loop가 한 번 수행될 때마다 물건이 하나씩 추가됨
4. 안쪽 for loop에서 w는 현재 물건을 넣을 수 있는 가능한 무게의 값(cur_w 이상)을 감소하면서 순회
5. 위 코드에서 dp 배열은 작은 인덱스의 값을 이용해 큰 인덱스의 값을 업데이트 하므로, 큰 인덱스 값부터 업데이트를 하면 이전 계산값이 손상되지 않음
6. dp[0]는 0으로 설정해야 원만한 계산 가능