앞서, 그리디 알고리즘을 통해 해결했던 배낭문제를 동적계획 알고리즘을 이용해서 해결해보자! 💡배낭문제의 부분문제를 찾아내기 4가지 요소 : 물건, 물건의 무게, 물건의 가치, 배낭의 용량 이중에서 물건과 물건의 무게는 부분문제를 정의하는데 고려 이유 : 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는 것과 안 담는 것을 현재 배낭에 들어있는 물건의 가치의 합에 근거하여 결정해야하기 때문 또한 물건을 배낭에 담으려고 할 경우, 배낭 용량의 초과 여부를 검사해야한다. 따라서, 부분문제를 아래와 같이 정의! K[i,w] = 물건 1~i 까지 (임시) 배낭의 용량이 w일 때의 최대 가치 i= 1~n, w= 1~C n : 물건의 개수, C: 배낭의 용량 여기서 C의 값이 매우 크면, 알고리즘의 수행시..