수식 만들기
배낭에 물건을 넣을 때 우리가 선택할 수 있는 2가지 경우:
- 물건을 넣는다
- 물건을 넣지 않는다.
IF 현재 내가 넣으려고 하는 물건의 무게가 전체 제한 무게를 초과한다면 선택지는 물건을 넣지 않는 것 밖에 없다.
B[k][W] = B[k-1][W] (if wk > W)
(W: 최대 무게, wk: k번째 물건의 무게)
IF 물건을 넣을 수 있는 무게가 조금이라도 남았다면 선택지는 다시 2가지가 된다.
- 새로운 물건을 넣지 않는다.
- (다른 물건을 빼서라도) 새로운 물건을 넣는다.
최대 가치를 원하기 때문에 두 경우 중 더 큰 값을 선택하게 될 것이다.
B[k][W] = max(B[k-1][W], B[k][W-wk] + val(wk)
현재 물건을 넣기 위해 넣었던 물건을 뺐을 때의 가치에 현재 물건의 가치를 더해주면 된다.
관련 문제:
12865번 - 평범한 배낭
https://www.acmicpc.net/problem/12865
Backend