[BOJ] 12865

평범한 배낭

12865번 https://www.acmicpc.net/problem/12865

Knapsack algorithm을 사용하는 문제입니다.
당연한 얘기겠지만 도둑은 가방에 물건을 챙긴다/챙기지 않는다 의 두가지 선택만 할 수 있습니다.
따라서, 첫번째 물건부터 N번째 물건까지 하나하나 확인해가며 i번째 물건까지 고려했을 때의 최댓값을 저장합니다.
i번째 물건까지 고려했을 때 가치의 최댓값은
i - 1번째 물건까지 고려했을 때 가치의 최댓값 또는 i - 1번째 물건까지 고려했을 때 가치의 최댓값 + i번째 물건의 가치
임을 이용하면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/12865.cpp