with with

0-1 Knapsack Promble은 각각의 가치(profit)와 무게(weight)를 갖는 여러 아이템을 가방에 추가하는데, 최대 가방이 담을 수 있는 무게를 초과하지 않는 범위에서 아이템의 가치가 최대가 되도록하는 아이템의 집합을 찾는 알고리즘이다. 이 문제를 접근하는 방법은 여러개가 있어 한 번에 소개해보고자 한다. Greedy Approach 그리디한 방법으로 해결하는 접근방식은 다음과 같다. 단위무게당 가격으로 내림차순 정렬을 하고, 무게가 가득 찰 때 까지 집어넣는 방식이다. 하지만 이 방식에는 문제가 존재한다. 바로 항상 최적해를 도출하지는 못한다는 것이다. 단, fractional knapsack problem의 경우에는 그리디한 방법으로도 최적해를 도출할 수 있다. (fractional..

Traveling SalesPerson Problem (Dynamic Programming) - 알고리즘 정의 주어진 Graph의 모든 노드를 한 번씩 방문하여 출발했던 노드로 돌아오는 방법 중, 가장 최단 시간으로 걸리는 경로를 찾는 문제이다. 일명 TSP 알고리즘이다. 위 예시에서는 v1 - v3 with611.tistory.com TSP문제는 DP방식으로 접근해 본 적이 있다. 이번에는 Branch and Bound방식을 사용해 접근해보려 한다. Branch and Bound 방식은 탐색(상태 저장) 공간을 트리구조를 이용한다는 점에서 백 트래킹 방식과 유사하 차이점은, 백 트래킹 방식은 앞서 언급한 적이 있듯 depth-first search 방식으로 탐색을 진행하며, 구현에 따라 모든(여러) 최..