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

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

 

blog.daum.net/sualchi/13721040

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

 

참고로 다음처럼 재귀 호출, 가지치기 기법으로도 작성할 수 있지만,

백준 온라인 저지 사이트에서는 시간초과 에러가 납니다. 

시간 초과를 피하려면 위 링크 게시물의 파이썬 코드를 참고하세요.

 

import sys
input = sys.stdin.readline
# 아이템 개수, 배낭 용량(최대 무게)
cnt, bw = map(int, input().split())  
iw, ig = [], []  # 아이템 무게와 가치 
gMax = 0    # 현재 최대 이득 
for i in range(cnt):
    w, g = map(int, input().split())
    iw.append(w)
    ig.append(g)
def solution(n, w, g):  # 사용할 아이템, 현재 무게, 현재 이득
    global gMax
    if n >= cnt:        # 사용할 아이템 없으면 되돌아 감
        return
    if gMax > sum(ig[n:]): # 남은 아이템 가치 합해도 최대보다 작으면
        return
    if w+sum(iw[n:]) < bw: # 남은 아이템 무게가 배낭에 다 들어가면 
        gMax = max(gMax, g+ig[n:]) # 나머지 가치와 최대 가치 비교 처리
        return
    if w+iw[n] <= bw:   # 선택 아이템을 합칠 때 배낭 용량 안 넘어가면
        if g+ig[n] > gMax:
            gMax = g+ig[n]
        solution(n+1, w+iw[n], g+ig[n])
    solution(n+1, w, g) # 다음 아이템으로 건너감 
#------------------------------------
solution(0, 0, 0) # 사용할 아이템 번호, 현재 무게, 현재 이득 
print(gMax)