코딩테스트
knapsack 알고리즘 (백준 1535 , 4781 , 7579 )
knapsack은 "제한된 자원" 으로 "최적(최대 or 최소) 의 이득" 을 얻는 문제에서 사용된다. 아래는 대표적인 예시 중 하나다. n개의 보석이있다. 이중 1~ n번째 보석중 k 번째 보석의 무게를 w_k, 가격을 c_k 라고 정의한다. 내가 가방에 최대로 담을 수 있는 무게가 w_max일때, 내가 담을 수 있는 최대 가치는? 대충 이런 느낌이지만, knapsack도 상황에 따라 다양한 방식으로 나눠져 있으므로 지금부터 같이 하나하나 알아보자! 1) fractional knapsack - 보석을 쪼개서 가방에 담을 수 있다. >> 그냥 무게당 가치가 높은것들을 우선적으로 가방에 담으면 끝이다. 예를들어 무게3에 가치 9, 무게 2에 가치 4 무게 1에 가치 1인 보석이있다고하면 1번의 무게 1당 ..
