문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력 1

4 7
6 13
4 8
3 6
5 12

예제 출력 1

14

나의 풀이

import sys
input = sys.stdin.readline

N, K = map(int, input().split()) #N = 물품의 수, K=무게 제한
dp = [[0]*(K+1) for _ in range(N+1)] #dp[i][j]: 처음부터 i까지의 물건을 살펴보고, 배낭의 용량이 j였을 때 배낭에 들어간 물건의 가치합의 최대값
weights = [0]
values = [0]
for _ in range(N):
    W, V = map(int, input().split()) #W = 각 물건의 무게, V = 해당 물건의 가치
    weights.append(W)
    values.append(V)

for i in range(1, N+1): #i번째 물건
    for j in range(1, K+1): #배낭 용량 j
        if j < weights[i]: #배낭 용량이 넣을 물건 무게보다 더 작아서 안 들어간다
            dp[i][j] = dp[i-1][j] 
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i]) 

print(dp[N][K])

풀이 과정

냅색 알고리즘, 배낭 문제라는 이름으로 유명한 문제인 것 같다.
담을 수 있는 물건이 나누어질 때(설탕 300g 등): 분할가능 배낭문제
담을 수 있냐 없냐 로만 판단할 때: 0-1 배낭문제 로 나뉘어 진다.

dp 리스트에 어떤 값을 넣어야 하는지도 감이 안와서 이 문제는 다른 풀이를 참고 했다.
dp 리스트에 들어가야 할 값은 물건을 처음부터 i번까지 살펴보고, 배낭의 용량이 j였을 때 배낭에 들어갈 수 있는 물건의 가치의 합의 최대값이다.
즉, 용량이 j일 때 제일 높은 가치는 몇인가? 를 담아야 한다는 것이다.
배낭에 한도가 아직 남았고, 남은 용량보다 더 작은 무게의 물건이 들어갈 수 있다면 그냥 넣으면 된다.
하지만 배낭의 남은 용량보다 더 큰 무게의 물건이 왔을 때 이 물건이 들어갈 수 있을 용량을 만들어서(즉, 앞서 담은 물건을 빼서) 이 물건이 들어갔을 때의 가치의 합과, 이 물건을 넣지 않고 그냥 지나갔을 때의 가치의 합을 비교해서 더 큰 값을 넣으면 되는 것이다.