[알고리즘]백트래킹(backtracking) 방법으로 푼 0-1 Knapsack 문제

소개글

백트래킹 방법으로 푼 0-1 배낭채우기 문제입니다.

promising()함수로 앞으로 자식 노드를 방문해도 유망한지를 검사하고,
유망하면 백트래킹 방법으로 자식노드를 방문합니다.

선택된 아이템셋을 출력하는 버전과,
실행시간을 측정하는 버전 두개로 구성되어있습니다.

주의사항:
프로그램을 실행하면, 콘솔화면에 아무것도 출력이 안되고, 커서만 깜빡거립니다.
여기서 숫자 1을 입력하면, 교재에 나와있는 아이템들로 문제를 해결하고,
2를 입력하면, 랜덤하게 아이템을 생성해서 문제를 풀게 되어있습니다.

목차

프로그램 1
▣ 개 요
▣ 소스코드
▣ 실행결과
▣ 결과 분석 및 토의

프로그램 2
▣ 개 요
▣ 소스코드
▣ 실행결과
▣ 결과 분석 및 토의

본문내용

▣ 소스코드
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<math.h> // for floor()
#define MAX 5

int numbest, maxprofit, W, n;
int w[MAX+1] = {0}; // item weight
int p[MAX+1] = {0}; // item profit
int include[MAX+1] = {0};
int bestset[MAX+1] = {0};
int selected[MAX+1] = {0}; // 출력용 : 자식노드 개수 저장

void InitItem(); // 아이템 생성
void knapsack(int, int, int); // 배낭채우기
int promising(int, int, int); // promising

참고 자료

Foundations of Algorithms using C++ Pseudocode