[백준/BOJ] 12865번: 평범한 배낭 (배낭 문제, 동적 계획법) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/12865 풀이N개의 물품 중에서 K 무게를 넘지 않도록 물품들을 배낭에 담았을 때, 담긴 물품들의 최대 가치값의 합은 얼마인가를 물어보는 문제이다. 배낭 문제라고 동적 계획법을 사용하는 유명한 문제이다.동적 계획법이란 전체의 문제를 작은 부분 문제로 나누어 계산한 후, 이 계산한 결과를 사용하여 전체의 문제를 빠르게 푸는 방법이다.이 방법은 부분 문제를 어떻게 규정해야 하는가가 가장 어려운 부분이라고 할 수 있다. 여기서는 부분 문제를 "N-1개의 물품 중에서 K 무게를 넘지 않도록 담았을 때, 최대 가치값의 합은 얼마인가?"로 잡았다.일단, 물품의 수를 계속 줄여가다 1개까지 줄어들면 계산은 아주 간단해진다.그리고 N-1..