배낭 알고리즘 (1) 썸네일형 리스트형 최적화 0-1 knapsack problem (배낭 채우기) 이번 글에서는 동적 알고리즘을 통해 0-1 knapsack problem (배낭 채우기)를 다뤄보도록 하겠습니다. 배낭 채우기 문제는 크게 탐욕 알고리즘을 이용한 fractional knapsack problem과 동적 알고리즘을 이용한 0-1 knapsack problem 이 있습니다. 주어진 배낭(배낭이 담을수 있는 한계 무게가 존재)과 여러 가지 물건(무게와 물건의 가치가 있는)들이 있습니다. 배낭에 최대한 많은 물건을 담으면서 최대한의 가치를 도출해 내는 문제입니다. 만약 여러분이 시계방을 털었을때 가져온 가방 안에 시계를 10개까지 담을 수 있다고 했을 때 스와치나 티쏘가 아닌 롤렉스나 IWC 같은 고가 혹은 그 이상의 시계를 털어야 한다는 개념(?)인 것입니다. 이것을 배운 도독이라면 제일 비.. 이전 1 다음
