0/1 배낭(Knapsack) 문제 동영상과 파이썬 예제 코드

0/1 배낭(Knapsack) 문제 해설 동영상과 파이썬 예제 코드

 

배낭에 물건을 최대 가치로 선택하여 넣을 때, 

각 물건이 한 개씩만 존재하는 경우 어떻게 해결하지를 다루는 동영상입니다.

동영상에서 그래프 구조, 재귀호출, 가지치기, 그리디 같은 알고리즘도 소개하고 있네요,

참고로 파이썬 코드는 아래에 있으니 참고하세요.(사전을 이용한 동적 프로그래밍 방식)

 

youtu.be/B_dLuVxbg-c

 

 

# 제로원 배낭 문제
# 사전을 이용한 동적 프로그래밍 예제 코드 
import sys
input = sys.stdin.readline
N, K = map(int, input().split()) # 아이템 개수, 배낭 용량 
bag = {0:0}
for _ in range(N):
    w, v = map(int, input().split()) # 아이템 무게, 가치 입력
    temp = {}                   # 임시 사전    
    for dw, dv in bag.items():  # 백에 있는 것들 가져오기
        nw, nv = dw + w, dv + v # 추가한 무게, 가치  
        if nw <= K:             # 배낭에 넣을 수 있을 때
            # 같은 무게일 때 더 높은 가치를 선택
            # get(nw, 0): nw 키가 없으면 0 반환
            temp[nw] = max(bag.get(nw, 0), nv)                                
    bag.update(temp) # 가방 업데이트 (무게별 최대 가치들로 갱신)
print(max(bag.values())) # 들어간 무게 중에서 가장 높은 가치 출력

[실행 결과]

4 20
4 4
7 7
5 6
6 7

 

24  <-- 답