다항시간근사해법 (1) 썸네일형 리스트형 [배낭문제 / Knapsack Problem] 다항 시간 근사 해법 (PTAS) 지난 포스트에서는 유명한 NP-난해(NP-hard) 문제 중 하나인 배낭 문제(knapsack problem)에 대해서 공부하였습니다. 어떤 문제인지 다시 정의하자면, 우리에게는 물건의 집합 \(I = \{1, \cdots, n\}\)와 배낭의 최대 하중 \(B \in \mathbb{Z}_+ \)가 주어집니다. 각각의 물건 \(i \in I\)에도 무게 \(w_i \in \mathbb{Z}_+\)와 가치 \( v_i \in \mathbb{Z}_+\)가 함께 주어집니다. 여기서 지난 시간과는 달리, 입력으로 주어지는 값 \(Z, w_i, v_i\) 모두가 (음이 아닌) 정수라는 가정을 하도록 하겠습니다.[ㄱ] 또한 어차피 무게가 \(B\)를 넘으면 가방에 담을 수도 없으니 무게가 \(B\)를 넘는 물건은 .. 이전 1 다음
