[Algorithm] 0-1 배낭 문제 이론 + 예제

❗0-1 배낭 문제란?

0-1 배낭 문제는 각 물건을 한 번만 선택하거나 아예 선택하지 않는 문제로 중복 선택이 불가하며 물건을 0번(선택하지 않음) 또는 1번(선택함) 선택할 수 있기 때문에 0-1이라는 이름이다. 최대 용량을 넘지 않으면서 가치의 합이 최대가 되도록 선택하는 방법이다.

 

❗예제

배낭의 최대 용량: k = 5

물건의 정보

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

 

물건1의 무게가 2이므로 용량이 2 이상일 때부터 넣을 수 있다. w=2 ~ w=5까지 물건1을 넣었기 때문에 3으로 갱신한다.

 

물건2의 무게는 3이기 때문에 w=3부터 w=5까지 넣을 수 있다. 이때 w=3, 4의 경우 물건1을 넣은 가치인 3보다 물건2을 넣은 가치 4가 더 크기 때문에 4로 갱신해 준다. w=5의 경우는 물건1의 무게 2와 물건 2의 무게 3을 모두 포함할 수 있으므로 원래의 값에서 물건 2의 용량만큼 추가한다.

 

물건3의 경우 무게가 4이므로 w=4, 5에 넣을 수 있다. w=4의 경우 물건2의 가치보다 물건3의 가치가 더 크기 때문에 물건3의 가치로 갱신하다. w=5는 더이상 집어넣을 수 없으므로 이전값을 유지한다.

따라서 배낭의 용량이 5일 때 가능한 최대 가치는 7이라고 할 수 있다.

 

❗예시 코드

N, K = map(int, input().split(" "))

bag = []
for _ in range(N):
    w, v = map(int, input().split(" "))
    bag.append((w, v))
bag.sort()

dp = [0 for _ in range(K+1)]

for i in range(len(bag)):
    w, v = bag[i]

    for j in range(K, w-1, -1):
        dp[j] = max(dp[j], dp[j-w]+v)

print(dp[K])

값을 갱신할 때는 배열의 맨 뒤에서부터 현재 물건의 무게까지 역순으로 순회해야 한 물건이 같은 단계에서 여러번 더해지는 문제를 방지할 수 있다.

dp[현재 무게] = max(dp[현재 무게], dp[현재 무게-담을 물건의 무게] + 담을 물건의 가치)

해당 점화식을 사용하여 최대 가치로 갱신할 수 있다.

 

 

❗관련 문제

https://www.acmicpc.net/problem/12865