무게 제한 t 안에서 값의 합을 최대로 만드는 문제다. 풀어본 건 같은 물건을 여러 번 담을 수 있는 형태다.
t = 5
v = [10, 20, 30, 50]
w = [ 5, 4, 2, 3]
무게 2와 3을 담아 정확히 5를 채우면 80이 답이다.
남은 용량에 계속 넣어보기
def rec(cur=0, val=0):
for i, weight in enumerate(w):
if cur + weight <= t:
rec(cur + weight, val + v[i])
else:
values.append(val)
values = []
rec()
ans = max(values)
지금까지의 무게와 값을 들고 다니면서, 들어가는 물건마다 담아보고 내려간다.
물건 목록을 매번 처음부터 다시 훑는다는 게 요점이다. 이미 담은 걸 빼지 않으므로 같은 물건을 몇 번이든 다시 담는다. 물건마다 하나씩만 있는 형태였다면 인덱스를 넘겨서 앞으로만 가게 해야 한다.
답을 모으는 자리가 좀 이상하다. 안 들어가는 물건을 만났을 때 values 에 넣는데, 물건 하나가 안 들어갈 때마다 넣으므로 같은 값이 여러 번 쌓인다. 마지막에 max 를 부르니 답은 맞지만 필요 없는 게 많이 들어간다.
정확히 채워야 끝나는 형태
같은 문제를 다른 파일에서 다시 풀었는데 종료 조건이 달랐다.
def func(cur_weight=0, cur_values=0):
global m
if cur_weight > capacity:
return
if cur_weight == capacity:
m = max(m, cur_values)
return
for i, n in enumerate(weights):
func(cur_weight + n, cur_values + values[i])
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
cur_weight == capacity 일 때만 답으로 친다. 용량을 정확히 채우는 조합만 세는 것이다.
용량이 남아도 되는 문제라면 이러면 안 된다. 위 값에서는 2+3으로 딱 맞는 조합이 최선이라 답이 7로 같게 나오는데, 무게가 전부 짝수인데 용량이 홀수인 경우처럼 딱 맞는 조합이 하나도 없으면 답이 아예 안 나온다.
왜 dp로 가야 하는가
두 코드 모두 같은 상태를 몇 번이고 다시 계산한다. 2 → 3 순으로 담은 것과 3 → 2 순으로 담은 것은 남은 용량이 같고 앞으로 할 수 있는 것도 같은데, 따로 끝까지 내려간다.
남은 용량이 같으면 그 뒤는 완전히 같다. 용량마다 최선의 값을 한 번씩만 구해두면 된다.