0-1 KnapSack Problem대표적인 DP 문제 알고리즘 중 하나로 알려져 있다. DP 란, 큰 문제를 작은 문제로 나누어서 푸는 방법을 일컫는 말이다.최적 부분 구조를 가진다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것입니다.처음에는 Brute Force 로 접근하였지만 시간 복잡도가 2 ^n 으로 시간 초과가 날것이 분명했다.DP 문제를 풀기 위해서는 '최적의 원리' (Principle of Optimality) 가 성립하는지를 확인해야 하는데,최적의 원리는 다음과 같다. "어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면.그 문제는 대하여 최적의 원리가 성립한다" 평범한 배낭 문제도 적용해 보자집합 A 를 n 개의 물..
