반응형 2017/06/109 [알고리즘] 동적 계획법(Dynamic Programming) - 6 동적 계획법(Dynamic Programming) - 6 이번 시간에는 동적 계획법의 또다른 고전 중에 Knapsack Algorithm에 대해 알아보자Knapsack은 배낭을 가리키는 말인데 배낭 알고리즘 이라고도 한다.이 알고리즘에는 재미있는 이야기가 숨어있는데, 도둑이 상점에 물건을 훔치기 위해 배낭 하나를 들고 왔다고 했을 때,가지고 나갈수있는 무게가 한정적이지만 최대의 비용을 낼 수있게 해야한다. 각각의 물건 마다 무게와 가격이 다 다르다.따라서 n개의 아이템과 배낭의 용량 W가 주어질 때배냥의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합을 구해야 한다.. 예를 들어 위의 그림에서 {1,2,5}는 가격의 합이 35,{3,4}는 가격의 합이 40,{3,5}는 가격의 합이46 이지만 배낭의.. 2017. 6. 10. 이전 1 2 3 다음 반응형