[DP][백준, 12865] 평범한 배낭

문제 풀이

최대 무게가 주어진 뒤, 개별 무게들을 통해 최대 가치를 구하는 문제이므로, DP로 풀 수 있다.

(DP 설명 : gaza-anywhere-coding.tistory.com/117)

 

코드 작성시 특징

뒤에서부터 반복문이 진행되도록 알고리즘을 작성하면, 훨씬 효율적으로 코드를 작성할 수 있다.

	앞에서 부터 수행	뒤에서 부터 수행
dp 배열 특징	이차원 배열	일차원 배열
반복문 수행	완전 이중 반복	"최대무게 - 무게단위" 만큼씩 수행

 

뒤에서 반복문 수행한 코드 (Better)

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

# input data
n, max_weight = map(int, input().split())
data = [tuple(map(int, input().split())) for _ in range(n)]  # weight, value

# dynamic programming
answer = -1
dp = [0] * (max_weight + 1)
for i in range(n):
    unit_weight = data[i][0]
    unit_value = data[i][1]
    for weight in range(max_weight, unit_weight-1, -1):
        dp[weight] = max(dp[weight], dp[weight - unit_weight] + unit_value)
print(dp[max_weight])

 

앞에서 반복문 수행한 코드 (Worse)

import sys
#sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

# input data
n, m = map(int, input().split())
data = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(n)]  # weight, value

# dynamic programming
answer = -1
dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for weight in range(1, m + 1):
        unit_weight = data[i][0]
        unit_value = data[i][1]

        if unit_weight > weight:
            dp[i][weight] = dp[i - 1][weight]
        else:  # unit_weight <= weight
            dp[i][weight] = max(dp[i - 1][weight], dp[i - 1][weight - unit_weight] + unit_value)
print(dp[n][m])