근사 알고리즘/Knapsack (2) 썸네일형 리스트형 [배낭문제 / 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\)를 넘는 물건은 .. [배낭문제 / Knapsack Problem] 0.5-근사 알고리즘 약간 발칙한 상상을 해봅시다. 여러분은 도둑이고 고가의 귀중품을 훔치기 위해 한 가게에 들어와 있습니다. 여러분의 눈앞에는 보기만 해도 휘황찬란한 물건들이 진열되어 있습니다. 당연히 모두 챙길 수 있다면 가장 좋을 겁니다. 하지만 이 물건들을 들고 가는 방법은 오직 여러분의 등에 매달린 배낭을 사용하는 것 뿐입니다. 배낭에는 최대로 견딜 수 있는 하중이 정해져 있고, 이를 초과하여 물건을 담는다면 배낭이 찢어져 버립니다. 배낭을 못 쓰게 된다면 손에 몇 개 쥐고 나오는 것 밖에는 방법이 없으니 큰 손해임이 분명합니다. 따라서 여러분의 목표는 배낭이 찢어지지 않을 정도의 무게로 가장 가치있는 물건들을 선택하는 것이 되겠죠. 이 문제가 바로 잘 알려진 NP-난해(NP-hard) 문제 중 하나인 배낭 문제(k.. 이전 1 다음
