백준 12865번: 평범한 배낭(Python)

문제

백준 12865번: 평범한 배낭

입출력

• 예제 입력
  4 7
  6 13
  4 8
  3 6
  5 12
• 예제 출력
  14

풀이

0-1 Knapsack 알고리즘

배낭 문제(Knapsack Problem 냅색 프라블럼)는 조합 최적화의 유명한 문제이다.
간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.
이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다.
위키백과 https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

dp로 해결할 수 있다

소스코드

import sys
N, K = map(int, sys.stdin.readline().rstrip().split())

def knapsack(N, K):
    ks = [[0 for _ in range(K+1)] for _ in range(N+1) ]
    for n in range(1, N+1):
        for w in range(0, K+1):
            value[n-1]
            if weight[n-1] <= w: # 물건의 무게가 배낭에 담을 수 있는 최대 무게보다 작거나 같음
                # 물건을 넣었을 때의 가치와 물건을 넣지 않았을 때의 가치 중 큰 값을 선택
                ks[n][w] = max(ks[n-1][w-weight[n-1]] + value[n-1], ks[n-1][w])
            else: # 물건의 무게가 배낭에 담을 수 있는 최대 무게보다 큼
                ks[n][w] = ks[n-1][w] # n-1번째 물건까지 담았을 때의 가치
    return ks[N][K]
    
value = []
weight = []

for i in range(N):
    w, v = map(int, sys.stdin.readline().rstrip().split())
    weight.append(w)
    value.append(v)
print(knapsack(N, K))

N : 물건의 수
K : 버틸 수 있는 무게
value : 물건들의 가치
weight: 물건들의 무게
ks[n][w] : n은 물건 번호, w는 배낭이 견디는 최대 무게
n번째 물건까지 배낭에 최대 w까지 담을 수 있다. 이 때 배낭에 담을 수 있는 물건들의 가치 합의 최댓값을 의미한다.

풀이 참고

[환상빛 별하늘] Reb∞t Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)