[BOJ] 평범한 배낭

---

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())    # 물건개수, 최대무게
s = [[0,0]]    # 각 물건의 (무게, 가치)

for _ in range(n):
    s.append(list(map(int, input().split())))

def knapsack():
    dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
    for i in range(n+1):
        for j in range(k+1):
            if i == 0 or j == 0:    # 최대무게 또는 물건 무게가 0이면 0으로 채움
                dp[i][j] = 0
            elif s[i][0] <= j:    # 현재 물건의 무게가 최대 무게보다 작은 경우
                # 현재 물건을 넣지 않는 경우 최대가치와
                # 현재 물건만큼의 무게를 빼서 현재 물건을 넣을 공간을 만드는 경우 최대 가치를 비교
                # 둘 중 큰 값이 최대무게
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-s[i][0]] + s[i][1])
            else:    # 현재 물건의 무게가 최대 무게보다 큰 경우
                dp[i][j] = dp[i-1][j]
    return dp[n][k]    # 물건 개수가 n이고 최대무게가 k일 때 최대 가치

print(knapsack())

결과

풀이 방법

• 배낭 문제(knapsack problem)의 대표적인 예시이다.
• 배낭문제는 물건을 나눌 수 있는 배낭 문제(fractional knapsack problem)와 물건을 나눌 수 없는 0-1 배낭 문제로 나뉜다.
• 전자는 각 물건의 단위무게당 가치를 가지고 가치가 높은 물건을 먼저 넣어보면서 greedy한 방법으로 해결할 수 있지만 후자는 다이나믹 프로그래밍 방법을 활용해야 한다.
• 물건의 수 0 ~ n, 최대무게 0 ~ k 일 때 각 경우의 최대가치를 저장할 이차원 배열 dp를 사용한다.
• 현재 넣을 물건의 무게가 최대 무게보다 작은 경우
• 최대 무게를 그대로 두고 현재 물건을 넣지 않을 때의 최대가치 dp[i-1][j] 와, 물건을 넣는 경우의 최대 가치 dp[i-1][j-wt] + vt 중 큰 값이 최대가치이다
• 현재 넣을 물건의 무게가 최대 무게보다 크면 넣을 수 없으므로 최대가치는 물건을 넣지 않을 때의 최대가치 dp[i-1][j]와 같다
• 위 과정으로 dp 배열을 채우면 가장 오른쪽 하단의 dp[n][k] 값이 n개의 물건을 가치고 최대무게 k 이하로 가방을 채울 때의 최대 가치이다.

---