Bestfit (1) 썸네일형 리스트형 0-1 Knapsack 알고리즘 (완전탐색, 분기한정) 냅색 알고리즘은 여러가지 방법으로 해결할 수 있다. 완전탐색, BFS, Bestfit, DP 까지.. 1. 완전탐색가능한 모든 경우의 수를 살펴보는 것이다. 2. 분기한정분기한정이란, 완전탐색에서 가지치기를 하는 것이라 생각하면 된다. 그러나 가지치기가 탈출조건을 걸어 여러번 탈출하는거라면, 분기한정이란 아직 자식을 확장하기 전에 이 자식이 진짜 '유망'한가를 확인한 다음 유망한 자식들만 확장하는 것이다. 즉, 유망하지 않은 자식은 확장하지 않는다.그렇다면, 이 자식이 유망한지 안한지를 확인할 수 있는 방법이 있어야하지 않는가? 맞다. 필요하다. 냅색 알고리즘에선 Greedy 방식으로 이 자식이 유망한지를 확인한다. Greedy 방식으로 냅색 알고리즘이 유망한지 판단하는 방법은 다음과 같다.물건의 가치를.. 이전 1 다음
