Depth first knapsack Algorithm

소개글

프로그램 개요
profit / weight 가 가장 높은 순으로 정렬된 아이템을 취할 때 W를 넘지 않으면서 최고로 취할 수 있는 답을 얻는 문제이다. 이 문제를 Backtraking 기법을 활용하여 Depth first로 풀이한다. 상태 공간 트리로 먼저 문제를 분석한 후 알고리즘화 하여 답을 얻는다. 간단히, 가치가 높은 기준의 아이템을 차례대로 넣는 경우와 안 넣는 경우로 나누어 첫번째 아이템부터 마지막 아이템까지 검색한다. 단, 유망한 노드와 유망하지 않은 노드를 구분하여 가지치기를 함으로써 좀 더 빠른 알고리즘이 가능하다. 이때, 유망성의 유무는 현재 얻은 최고의 profit보다 bound(최대치)가 낮으면 그 노드는 더 이상 유망하지 않다. 다른 하나는 W를 넘게 되면 유망하지 않다.

컴파일 실행환경

GNU Gcc / Debian Linux

참고 자료

없음