배낭 문제

배낭 문제

n개의 물건과 각 물건 i의 무게 w_i와 가치 v_i가 주어지고, 배낭의 용량이 C일 때, 배낭에 담을 수 있는 물건의 최대 가치를 구하는 문제 (각 물건은 1개씩만 존재)

 

---

배낭의 용량이 0(kg)부터 1(kg)씩 증가하여 최종 용량인 C(kg)가 될 때까지 변화시켜 가며 배낭의 용량 내에서 어떤 물건을 담았을 때 가치가 더 커지는지를 결정

 

임시 배낭 용량 : 배낭 용량은 C(kg)이지만 배낭 용량이 0(kg)부터 1(kg)씩 증가할 경우의 배낭 용량 

K[i, w] = 물건 1 ~ i까지만 고려하고, (임시) 배낭의 용량이 w일 때의 최대 가치

∴ K[n, C] = 구하고자 하는 최종해

 

두 가지 경우가 존재

① 물건 i의 무게 > 임시 배낭 용량

② 물건 i의 무게 <= 임시 배낭 용량

① 물건 i의 무게 > 임시 배낭 용량

물건 i를 배낭에 담지 못함

따라서 K[i, w] = 물건 i를 담기 전(물건 i-1일 때) 최대 가치 = K[i-1, w]

② 물건 i의 무게 <= 임시 배낭 용량

물건 i를 배낭에 담을 건지, 담지 않을 건지 결정

만약 i를 담았을 때, 담지 않았을 때보다 최대 가치가 커진다면 i를 담고, 그렇지 않다면 i를 배낭에 담지 않을 것

 

- i를 담지 않을 경우는 ①과 같이 K[i, w] = K[i-1, w]

 

- i를 담을 경우에는 배낭의 무게(용량)가 w에서 물건 i의 무게인 w_i만큼 더 추가됨. 따라서 현재 배낭의 용량인 w를 초과하게 되어 물건 i를 추가로 담을 수 없음.

그러므로 담고 싶으면 물건 i의 무게인 w_i를 배낭에 마련해 줘야 함(현재 용량 w에서 w_i를 빼서 w_i가 추가됐을 경우 배낭의 용량을 초과하지 않도록 맞춤)

즉, 물건은 i-1까지 고려하고 배낭 용량은 w-w_i일 때의 최대 가치에서 담으려고 하는 물건 i의 가치 v_i를 더하여 최대 가치 K를 구함

K[i, w] = K[i-1, w-w_i] + v_i

 

이 두 가지 경우 중 큰 값이 K[i, w]

 

---

예제

배낭 용량(C) = 10(kg)

물건 1) 가치: 10, 무게: 5

물건 2) 가치: 40, 무게: 4

물건 3) 가치: 30, 무게: 6

물건 4) 가치: 50, 무게: 3

참고) 알기 쉬운 알고리즘

 

 

class Product:
    def __init__(self, w, v):
        self.weight = w
        self.value = v
        
def knapsack_dp(capacity, items):
    n = len(items)  # 물건 개수
    K = [[0] * (capacity + 1) for _ in range(n)]    # 용량은 0부터 10까지, 물건은 4개
    
    for i in range(n):  # 물건 i(물건0 ~ 물건3)
        for w in range(1, capacity + 1):
            # w=0일 때는 아무것도 담을 수 없음(배열 만들 때 이미 0으로 초기화 해두었기 때문에 1부터 값 갱신)
            if(items[i].weight > w):
                K[i][w] = K[i-1][w]	# 파이썬은 음수인덱싱 가능
            
            else:
                K[i][w] = max(K[i-1][w], K[i-1][w-items[i].weight] + items[i].value)
                
        print(K[i])
        
    return K[n-1][capacity]
    
        

# 실행
if __name__ == '__main__':
    items = [Product(5, 10), Product(4, 40), Product(6, 30), Product(3, 50)]
    value = knapsack_dp(10, items)
    
    print(f"최대 가치는 {value}")

 

실행 결과