문제
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 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)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
고민
이 문제는 조건에 따라 주어진 상황에서 최적인 값을 구하는 최적화 문제이다. 무식한 방식으로 풀어본다면 모든 물품의 무게와 가치를 저장하고 이들의 조합이 무게 K를 넘지 않으며 더 큰 최댓값을 가지는지 하나하나 따져볼 수 있으나 당연히 터무니 없는 시간이 소요된다.
가능한 한 연산을 줄이는 방법은 조건에 부합하면서 최대의 가치 합을 계산해두며 이 값들을 이용해서 다음 아이템을 넣을지 말지 고려하는 것이라고 생각했다. 즉, 동적 프로그래밍을 이용하는 것이다.
우선 큰 문제를 작게 분해 해보았다. i번째 물품을 배낭에 넣을지 말지 고민한다고 할때, 넣는다고 할 때에는 넣을 수 있는 경우중 최대인 값에 더하고, 넣지 않는다고 할 경우 i-1번째 물품을 고려한 다음 가장 큰 값을 선택해보려 했다.
하지만, i번째 물품의 무게만큼 여유가 남는 경우를 찾기 위해선 이전에 수행했던 과정을 한 번 더 살피며 들어갈 배낭을 찾아야 했다. 그리고 넣은경우 안넣은 경우를 분리해서 생각하다보니 풀이가 복잡해져 다른 방식을 찾아야했다.
해결
어떤 물품이 들어왔을 때, 이물품만 들어있는 배낭과 무게 K를 넘지 않으며 다른 물품과 함께 넣는 배낭이 모두 존재한다면 편리할 것이다.
그리고 이런식으로 여러 배낭을 둘 때 여러 물품의 무게 합이 a인 물품들을 배낭에 넣을 경우와 무게가 a인 물품을 배낭에 넣을 경우는 그냥 두 상황의 가치합만 비교하여 더 큰 경우만 남겨두면 되므로 간편하다.
물품 개별 무게나 물품들의 무게 합이 어찌됐든 간에 배낭의 무게는 K를 넘을 수 없다. 당연히 최종 결과에서도 K 이하의 무게만 갖는 배낭만 보면 된다.
그러므로 K + 1개의 공간을 미리 선언해두고 이것을 배낭으로 한다. i번 배낭은 무게합이 총 i인 배낭으로 여러 물품의 무게합일 수도 있고, 단일 물품의 무게일수도 있다. 단지 저장하는 값은 무게가 i인 경우 나올 수 있는 최대 가치이다.
어떤 물품의 무게가 a일 때, a <= a+i <= K를 만족시키는 i에 대해서
(BP는 배낭 배열의 이름)
BP[a+i] 는 무게가 i인 배낭에 무게가 a인 물품을 넣었을 때 배낭의 가치이다.
무게가 i인 배낭에 새 물품을 넣었을 때 가치와 기존 BP[a+i] 배낭에 있던 가치를 비교해 더 큰값을 저장하게 한다.
이 연산을 i = 0부터 a+i가 K 이하인 동안 i를 1씩 증가시키며 반복한다.
내가 제출한 코드에선 K부터 물품의 무게까지 1씩 감소시키며, 최대 가치값을 갱신하는데, 반대방향으로 갱신하면 갱신된 값을 이용해 계산해서 올바른 가치보다 더 큰 값이 되어버린다.
그리고 만일에 대비해서 BP[a+i]의 가치를 정할 때 BP[i]가 0(배낭이 비어있음)이라면 연산이 수행되지 않도록 하였다.
import sys
n, k = list(map(int, sys.stdin.readline().split()))
backpack = [0 for i in range(k+1)]
items = [[0,0]]
for i in range(n) :
# index 0 : weight, index 1 : wealth
items.append(list(map(int, sys.stdin.readline().split())))
for j in range(1, n + 1) :
for s in range(k, items[j][0] - 1, -1) :
if s == items[j][0] or backpack[s - items[j][0]] :
backpack[s] = max(backpack[s - items[j][0]] + items[j][1], backpack[s])
print(max(backpack))