0-1 Knapsack Problem (0-1 배낭 문제) - 전체 C 코드, 입력 데이터셋 및 출력 결과 포함

소개글

0-1 Knapsack Problem에 대해 세 가지 방법을 구현하고, 입력 자료에 대해 최대 이윤과 해벡터 및 수행 시간을 출력하는 프로그램을 작성하여라. 정렬 알고리즘은 최소힙(min-heap)을 사용하는 힙 정렬을 이용하여라.
(방법 1) Depth-first search with branch-and-bound
(방법 2) Breadth-first search with branch-and-bound
(방법 3) Best-fit search with branch-and-bound

< 포함 사항 >
- 0_1_knapsack.cpp (전체 코드)
- 0_1_knapsack.h (헤더 파일)
- ProgrammingReport3.hwp (보고서)
- p3data0~6.txt (입력데이터셋)
- p3data0~6.jpg (출력 결과)

목차

1. 문제 설명

2. 입출력의 예
(1) 입력 자료 형식의 예
(2) 출력 형식의 예 (각 방법에 대해)

3. 문제풀이 방법 (알고리즘)

4. 소스 코드

5. 수행 결과

6. 결과 분석 및 토의

본문내용

방법 1(depth first search with branch-and-bound)의 경우 재귀함수를 호출하여 자식 노드를 생성하는 방식으로 구현하였다. 현재 object를 include 하는 경우와 하지 않는 경우, 이렇게 두 가지로 나뉘어 각각 left child와 right child로 구분된다. 재귀 함수 호출을 위한 stack은 따로 구현하지 않았다. solution vector는 한 번만 출력하였는데, solution vector는 방법 1에서 구하여 출력하였다. 이 solution vector를 구하기 위해 현재 상태가 최대 이윤인 경우(최대 무게보다 작거나 같은 상황에서) 현재 상태를 따로 저장해두었다.
방법 2(breadth first search with branch-and-bound)의 경우 queue를 통해 노드를 생성하는 방식으로 구현하였다. 방법 1에서 stack을 사용한 것이라면 여기서는 queue를 사용한 것이다. 방법 1과 마찬가지로 현재 object를 include 하는 경우와 하지 않는 경우, 두 가지로 나뉘어 각각 left child과 right child로 구분하여 생성하였다. 재귀함수 호출 대신 단일 반복문을 사용하여 구현하였다.
방법 3(best-fit search with branch-and-bound)의 경우 priority queue를 통해 노드를 생성하는 방식으로 구현하였다. 방법 1의 stack과 방법 2의 queue 대신 priority queue를 사용하는 방식이다. 여기서 priority queue는 heap의 형태로 구현하였다. 그렇지만 heap sorting에 사용된 heap과는 달리 max heap의 형태로 구현하였다. 다른 방법들과 마찬가지로 현재 object를 include 하는 경우와 하지 않는 경우, 두 가지 각각 left child와 right child로 구분하여 생성하였다. 재귀함수를 호출하지 않는 대신 단일 반복문을 통해 구현하였다.

참고 자료

없음

압축파일 내 파일목록

0_1_knapsack.cpp
0_1_knapsack.h
input output/
input output/p3data0.JPG
input output/p3data0.txt
input output/p3data1.JPG
input output/p3data1.txt
input output/p3data2.JPG
input output/p3data2.txt
input output/p3data3.JPG
input output/p3data3.txt
input output/p3data4.JPG
input output/p3data4.txt
input output/p3data5.JPG
input output/p3data5.txt
input output/p3data6.JPG
input output/p3data6.txt
ProgrammingReport3.hwp

전체 목록 보기