[알고리즘] Knapsack Problem

소개

Knapsack Problem 구현 및 소스 입니다.

목차

◎ 배낭채우기 알고리즘
◎ 주어진 아이템 데이터
◎ 실제 입력되는 데이터 (◇ n=30 W=100 경우)
◎ 실제 입력되는 데이터 (◇ n=30 W=70 경우)
◎ 결과 화면
◎ 소스코드

본문내용

◎ 배낭채우기 알고리즘



상태공간트리의 각노드에서 추정할수 있는 이득의 상한이 지금까지 조사된 해들중에서 가장 좋은 해의 값(이득의 하한)보다 같거나 작은면 퇴각한다.
같은 입력에 대해 0/1배낭 문제와 분할 가능 배낭 문제의 해를 비교해볼 때, 분할 가능 문제의 해는 0/1배낭문제의 해를 비해 항상 총 이득이 같거나 크는 것을 알 수 있다. 그래서, 분할가능 문제의 해는 0/1 배낭 문제의 해에 대한 상한으로 설정할 수 있다. 결과적으로 상태공간트리의 각 노드 x에서 이득의 상한 값은 bound를 다음과 같이 설정할 수 있다.

bound(x) = 현재까지 선택된 물건들의 이득의 합 +
남은 물건들과 남은 용량에 대한 분할 가능 배낭 문제의 해의 이득

상태공간트리의 각 노드 x를 방문할 시점 까지 조사된 최고 이득을 maxprofit이라고 설정하면,
x에 대한 한계 함수는 다음과 같이 설정할 수 있다.

◇ 노드 x에서 선택된 물건들의 무게의 합이 W를 초과하면 퇴각한다.
◇ 노드 x에서의 상한 bound가 maxprofit보다 같거나 작으면 퇴각한다.

◎ 주어진 아이템 데이터

참고자료

· 없음