- 0 - 1 다단계배낭기법
- ㆍ 저자명
- 권치명,정성진,Gwon. Chi-Myeong,Jeong. Seong-Jin
- ㆍ 간행물명
- 한국국방경영분석학회지
- ㆍ 권/호정보
- 1984년|10권 1호|pp.57-63 (7 pages)
- ㆍ 발행정보
- 한국국방경영분석학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
The 0-1 multi-period Knapsack problem (MPKP) has a horizon of m periods, each having a number of types of projects with values and weights. Subject to the requirement, the cummulative capacity of the problem in each period i cannot be exceeded by the total weight of the projects selected in period 1, 2, ..., i. It is a problem of selecting the projects in such a way that the total value in the knapsack through the horizon of m periods is maximized. A search algorithm is developed and tested in this paper. Search rules that avoid the search of redundant partial solutions are used in the algorithm. Using the property of MPKP, a surrogate constraint concerned with the most available requirement is used in the bounding technique.