1. 이게 뭘까?
knapsack 알고리즘.
도둑이 용량이 한정된 가방을 가지고 물건을 훔치는데 최대한의 가치를 얻고자 할때.
어떤 조합으로 물건을 가방에 집어넣어야 특정 가치가 최대가 되는지 확인할 수 있는 알고리즘
2. 이걸 어디에 쓸까?
아직 잘 모르겠음...
여러 조합이 나열되어있을때 특정 조건의 최대를 만족하는 조합을 찾고싶을때? 도대체 그런경우가 뭐지?? (추후에 깨닫게 된다면 업로드 예정. 잘 아시는분 댓글로 알려주세요 :)
3. 이게 왜 좋을까?
우선 왜 좋을까 를 다루기 위해서는 다이나믹 프로그래밍을 적용시켜야 한다. 사실 최대값을 가지는 조합을 구하는 방법으로는 단순 무식하게 완전탐색을 쓴다거나 permutation 을 사용하는 방법도 있다. 하지만 그건 시공간 복잡도를 전혀 고려하지 않은 방법이다. 즉, 탐색범위에 따라 불가능한 문제가 될 수 있다.
그러므로 '한번 계산한 값은 다시 계산하지 않고 그대로 사용하는' 다이나믹 프로그래밍을 사용하여 최대값을 구하는 조합을 가장 단순화 시켜; (=> 특정 번호의 물건을 1. 넣을 수 있을때 2. 넣을 수 없을때) 각각의 순간에서 최대값을 저장하는 DP테이블을 만들고 값을 알아낸다.
번외
knapsack algorithm 에도 seperable 과 0/1 로 나뉜다. 위에서 설명한 접근방식은 0/1 즉, 넣을때, 안넣을때 로 나누어서 dp 테이블을 채워나가는 방식이다. seperable 은 '금가루'와 같이 무게와 가치가 있으나 무게를 쪼갤수 있을때, 최대의 가치를 만족하는 경우를 찾아나가는 상황이다.
쪼갤 수 있기때문에 어느 순간에나 최선의 선택을 하는 방법이 동일하며 이는 '그리디 알고리즘'에 속한다.
