반응형
다이나믹프로그래밍동적계획법
-
알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem)알고리즘 2020. 11. 6. 14:42
탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 설정해서 구하기 때문에 과잉이라 볼 수 있다. 반면 탐욕 알고리즘은 항상 최적인 해를 만들어 주지 않는다. 그래서 보통 반례를 통해 최적의 해를 갖지 않는다는 것을 증명한다. 이 두 방법의 차이점을 확실하게 이해하기 위해서 0-1배낭 채우기와 배낭 빈틈없이 채우기라고 하는 두가지 문제를 살펴본다. 우선 결론적으로 말하면 배낭 빈틈없이 채우기 문제는 탐욕 알고리즘을 이용해서 풀 수 있지만 0-1배낭채우기를 풀 수 없으며 대신 동적계획법을 이용해서 완벽하게 풀 수 있다. < 0-1배낭채우기 문제(0-1 knapsack prob..