개요 0-1 배낭 문제는 n개의 물건에 대해 최대 가치가 되도록 담는 알고리즘이다. 시간복잡도 분석 각각의 물건은 넣는다 / 넣지 않는다의 2개의 경우가 있으므로 단순히 시간 복잡도를 계산하면 O(2^n)이다. Dynamic Programming으로 해결 i > 0이고 w > 0일 때, 전체 무게가 w를 넘지 않도록 i번째까지의 항목 중에서 얻어진 최고 이익을 P[i][W]라고 하면 P[i][W]는 다음과 같이 구할 수 있다. 이 알고리즘의 시간복잡도는 이다. W = 10이고, 품목이 다음과 같을 때의 0-1 배낭 문제 예시 문제점 불필요한 항을 계산한다. (위 그림에서 P[3][8]과 P[3][9]를 구할 필요는 없다.) 위 그림의 경우 총 n(4) * W(10)의 40번의 비교가 필요하다. 아래와 같..
