[백준/12865/Gold V] 평범한 배낭 - DP, 냅색 알고리즘 with Python

문제✅

평범한 배낭 (🥇골드 5티어)

풀이

WHY? 알고리즘 선택 이유

• 냅색 알고리즘 : 한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제
  • 냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다. 담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem) 담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem)

 

HOW? 어떻게 풀었는가

해당 문제는 0-1 배낭문제의 경우

1. 물건마다 1~최대무게 K까지 배열을 가짐 -> 0번인덱스는 0으로 초기화해둠

• knapsack[i][w] 의 의미 = 1번째~i번째 물건까지 w무게를 만들기 위한 최대 값
• knapsack[i][w] 값 판단 로직

1. w >= i번째 물건의 물건 : 현재 물건 포함할 수 있음 -> max(현재 물건 값+ i-1번째 물건까지의 나머지 무게(w-현재물건무게)를 만드는 최대 값 or i-1번째 물건까지의 최대 값)
2. w < i번째 물건의 물건 : 현재 물건은 포함할 수 없는 무게임. -> i-1번째 물건까지의 최대값을 대신 저장한다.

 

POINT! 기억할 부분

import sys
input = sys.stdin.readline
n, k = map(int, input().split()) #개수, 최대무게

ks = [[0] * (k+1) for _ in range(n+1)] # 1~n 행에 대해서 냅색 알고리즘 시작

# 시간 복잡도 : O(nk) -> 최대 10,000,000
# i 번째 물건
for i in range(1, n+1):
    w, v = map(int, input().split()) #무게, 값

    # i 번째 물건까지 탐색했을 때, 무게 weight을 만들기 위한 최대의 값을 저장함
    for weight in range(k + 1):
        # 현재 물건 무게가 더 클 경우 - 포함할 수 없으니, 이전 단계에서의 최대값을 저장한다.
        if w > weight:
            ks[i][weight] = ks[i-1][weight]
        else:
            # 더 큰 값 저장 : 현재 물건 무게+이전 단계에서 남은 무게 채우는데 필요한 최대값 OR 이전단계에서의 최대값 
            ks[i][weight] = max(v + ks[i-1][weight-w], ks[i-1][weight])

#마지막에 저장된 값이 최종
print(ks[n][k])