|
여러 가지 NP 완전 문제
|
|
■ 0-1 배낭(knapsack) 문제
- 배낭의 용량이
c이고, n개의 물체마다 무게 wi, 그 물체를 배낭에 넣었을
때 발생하는 이익 pi이다. 변수 xi는 물체 I가 배낭에 들어가면
xi=1, 그렇지 않으면 xi=0의 값을 갖는 것으로 정의한다.
이 경우 0-1 배낭 문제에 대한 최적화(optimization) 형태와
판정(decision) 형태는 다음과 같다.
-------------------------------------------------------------------------
최적화 문제 :
wixi
<= C 이면서 pixi를
최대로 하는 xi를 구하라.
판정 문제 : wixi
<= C 이면서 pixi
>= R인 xi, 1<= i <= n 들의 값이 존재하는가?
-------------------------------------------------------------------------
- 위와 같이 보면
판정문제가 상당히 제한적인 것으로 생각될 지 모르나 배낭
문제에 대한 최적화 문제의 해를 구했다면 그 해에 대한
최대값이 R보다 큰지 비교하면 바로 판정문제도 풀린다.
반대로 판정문제의 해로 최적화문제의 해를 구할 수 있다.
| 
