[백준/다이나믹 프로그래밍 2] - 평범한 배낭

문제 링크

코드

# 무게 w, 가치 v, 최대 무게 k일 때
# 들 수 있는 물건들의 가치의 최댓값 구하기
# 무게 순으로 오름차순 정렬하면 실패.
# 가치 순으로 내림차순 정렬하면 성공.
# 정렬하지 않고, 초기 입력 순서 그대로 해도 성공
n, k = map(int, input().split())
stuffs = [list(map(int, input().split())) for _ in range(n)]

# 가치 순으로 내림차순 정렬(성공)
# stuffs.sort(key=lambda x: -x[1]) 

# dp[i] = 무게 i일 때 담을 수 있는 최대 가치
dp = [0] * (k + 1)

for stuff in stuffs:
    w, v = stuff
    
    for i in range(k, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)

print(max(dp))

풀이

문제의 목표

• 배낭에 넣을 수 있는 물건들의 가치의 최댓값 구하기

2가지 방식으로 풀어 보았다.

• 가치 순으로 정렬하기
• 정렬하지 않기

일단 정렬을 한다면 무게 순으로 정렬하면 실패한다. 왜 그런지 정확한 이유는 모르겠으나, 추측컨대 가치의 최댓값을 구해야 하기 때문인 것 같다.

그래서, 가치 순으로 내림차순으로 정렬해야 한다. ➡️ stuffs.sort(key=lambda x: -x[1])

점화식은 아래와 같다.
dp[i] = 가방의 무게가 i일 때 담을 수 있는 최대 가치

가치가 큰 물건부터 먼저 가방에 넣어보면서 비교하는 것이다. 단, 가방의 무게가 k를 넘어서는 안된다.

물론 정렬을 하지 않고도 풀 수 있다.