0-1배낭채우기
-
알고리즘: 되추적(BackTracking)을 이용한 0 - 1 배낭채우기 문제(0- 1 knapsack problem) 공부하기알고리즘 2020. 11. 15. 00:33
이전에는 동적계획법을 이용하여 0-1 knapsack 문제에 대해 다루었다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 이번 포스팅은 좀 더 효율적인 0-1 knapsack problem 알고리즘에 대해 알아본다. 기존의 0-1 knapsack problem은 상태공간트리에서 되추적을 이용하였다. 이 문제는 최댓값을 구하는 최적화 문제이기때문에 검색이 완전히 끝나기 전까지는 마디가 해답을 포함하고 있는지 알지 못한다...
-
알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem)알고리즘 2020. 11. 6. 14:42
탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 설정해서 구하기 때문에 과잉이라 볼 수 있다. 반면 탐욕 알고리즘은 항상 최적인 해를 만들어 주지 않는다. 그래서 보통 반례를 통해 최적의 해를 갖지 않는다는 것을 증명한다. 이 두 방법의 차이점을 확실하게 이해하기 위해서 0-1배낭 채우기와 배낭 빈틈없이 채우기라고 하는 두가지 문제를 살펴본다. 우선 결론적으로 말하면 배낭 빈틈없이 채우기 문제는 탐욕 알고리즘을 이용해서 풀 수 있지만 0-1배낭채우기를 풀 수 없으며 대신 동적계획법을 이용해서 완벽하게 풀 수 있다. < 0-1배낭채우기 문제(0-1 knapsack prob..