12865번: 평범한 배낭

출처 : https://www.acmicpc.net/problem/12865

문제 요약

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. dp문제를 보면 PTSD가 오는데 역시나 혼자 힘으로 풀지 못하였다...

문제 풀이

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [[0] * (k+1) for _ in range(n+1)]
arr = [[0, 0]]
for _ in range(n):
    arr.append(list(map(int, input().split())))
for i in range(1, n+1):
    for j in range(1, k+1):
        w = arr[i][0]
        v = arr[i][1]
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
print(dp[n][k])

다른 접근

1차원 dp로도 풀 수 있는 방법을 알게 되었다.

# 1차원 dp
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [0 for _ in range(k+1)]
arr = []
for i in range(n):
    w, v = map(int, input().split())
    for j in range(k, -1, -1):
        if j >= w:
            dp[j] = max(dp[j-w] + v, dp[j])
print(max(dp))