[백준] 평범한 배낭
DP
백준
medium
문제
준서가 여행에 필요하다고 생각하는 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)가 주어진다.
4 7
6 13
4 8
3 6
5 12
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
14
DP로 1~K 무게까지 N개의 베낭을 넣었을 때 최대 가치값을 저장해둔다.
- N개의 베낭을 순회하면서, 1~K 무게까지 넣을 수 있는 최대 가치값을 배열에 저장해둔다.
- K 무게를 N weight값으로 넣을 시, 내 자신을 넣고, K-내무게에 넣을 수 있는 가치를 그냥 더해만 주면 된다.
문제에서는 최대 가치값만 출력하라고 했지만, 어떤 무게값을 넣었을 떄 최대 가치값에 도달하는지 같이 보기 위해서 k 개의 배열을 선언하고, 해당 배열에 무게의 노드들을 append 했다.
# 0으로 boundary를 만들어준다. 초기화 값으로 쓰기 위해
dp = [[0] * (k+1) for _ in range(n + 1)]
detail = [list() for _ in range(k + 1)]
for i in range(1, n+1): # 베낭 수 만큼 순회
w, v = map(int, input().split())
for j in range(1, k+1): # 무게 만큼 순회
if j < w:
dp[i][j] = dp[i-1][j] # 각 n의 루프마다, 최대값을 갱신하는 것이기 때문에, 전 회차의 값을 그대로 이관한다.
# dp[i][j] = 0 이렇게 하면 안된다.. 전 회수의 max가 있을 수 있기 때문에
else:
if dp[i-1][j] < v + dp[i-1][j-w]:
detail[j] = list() # 초기화
detail[j].append(w)
if len(detail[j - w]) > 0:
detail[j] += detail[j-w]
dp[i][j] = max(dp[i - 1][j], v + dp[i - 1][j - w])
print(dp[n][k])
print(detail[k])
# 무게 K에 대한 최대 가중치를 다음 케이스에서도 사용할 수 있으므로 재활용된다 -> DP 특징
# 어떤 베낭을 넣어서 해당 최대 가중치를 도달했는지는 확인 불가하다. dp[][]배열의 값을 최대값으로 정했기 때문에