|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
06/05/25 00:57
음 이건 빠르게 풀 수 있는 알고리즘이 없지 않나요?? 자를 수 있는 금괴면 빠르게 풀 수 있지만 이건 하나하나 다 대입해 봐야 되는 문제 아니었나...
06/05/25 01:05
0/1 Knapsack은 NP problem입니다.
모든 조합을 다 넣어보는 수 밖에 없죠. 그러나 search하는 방법들간의 효율이 다르긴 합니다. 최적해를 보장하는 효율적인 search 방법이.. 기억이 안나는군요-0- 강의 노트 다시 찾아봐야겠습니다.
06/05/25 01:15
무슨 백트래킹 다이나믹(?) 이런걸로 푸는방법도 있다고 하고
당최먼말인지; C(i)=(무게가 i일때 최대 이익), C(i)=max C(i-w[k])+p[k] | k=1..n
뭐 이런 점화식으로 풀어야할 문제인가요; 에이포한장에 조리있게-_- 제출하라 그랬는데 한줄쓰기는 좀ㅠ
06/05/25 01:39
촉호파이 // 아마 그 점화식으로 못 풀 겁니다... 그 점화식 자체가 무게가 늘어날 때 마다 n 배의 가지수가 생기므로 -_-;;
06/05/25 02:10
제 생각에는 search algorithm중 괜찮은거 몇 가지를(혹은 하나를) 정리해 오라는 게 숙제일 듯 하네요.
실제로 푸는 건... size커지면 답 없죠.
06/05/25 02:11
그 백트래킹은..
initial solution을 정하고, 그 solution에서 a(속한 것 중 아무거나 선택)를 빼고 아직 선택 안한 것들 중 하나인 b를 넣었을 때, 가장 해가 많이 개선되는 a,b의 조합을 골라서 바꾸는 방식으로 해를 개선해 나가는 형태입니다. 아마.. globally optimum을 보장하진 않을 건데요.
06/05/25 03:33
흠 촉호파이님이 위에 적으신거는 아마 한 금괴를 여러번 담는 에러를 범하므로 안될것 같네요 문제 조건에 금괴가 무한개 있다는건 아닌것 같고.
항즐이님 답변도 항즐이님이 말하듯이 globally optimum이 나오지 않죠 흠 물론 저도 확신은 할 수 없다만은 한번 적어보겠습니다. f(i,y ) = i 번째 금괴까지 검색했을때 y 무게를 넣을수 있을때 최적값 f(i, y) = f(i + 1, y) y < wi 일때 f(i, y) = max f(i+1, y), f(i + 1, y- wi) + pi y>= wi 일때
입니다. 결국 백트래킹으로 다 탐색하는거죠
06/05/25 03:36
흠 정리해서 다시.
금괴가 한개 일때 for the first decision is xi= 1. The case xi= 1 은 only when y >= wi. From the principle of optimality, it follows that f(i,y) = f(i+1,y-wi) + pi. 위의 두 경우를 통해 f(i,y) = f(i+1,y) whenever y < wi. f(i,y) = max f(i+1,y), f(i+1,y-wi) + pi , y >= wi.
06/05/25 08:25
이 문제의 경우 fondation of algorithm 이라는 책에 branch-and-bound 라는 기법을 통한(back-tracking 하는 도중 greedy aproach를 통해 pruning을 함)방법과 dynamic programming 을 통한 방법을 통해서 시도하는 방법을 동시에 다루고 있습니다. 후자보다는 전자쪽에 비중을 많이 두어서 설명하는걸로 기억합니다.
이책은 수업교재가 아니더라도 도서관에는 왠간해선 다있으니 찾아보심이 나을꺼고요... 다른 학교는 어떤 교재를 쓰는지 궁금하네요... 뱀꼬리가 길었는데, 가방이 어느정도 작은량일때(한 10만정도?) 는 dynamic programming, 그렇지 아니할떄는 branch-and-bound 를 적절히 골라쓰면 될꺼 같네요~ 그럼...
06/05/25 13:42
가방안에 얼마나 아이템을 잘 넣어야 최고로 넣을 수 있는 가 하는 문제입니다.
결국엔 제한된 아이템 가운데 몇개를 선택하는 문제인데, 그 선택한 아이템들의 조합이 가장 최적인가를 쉽게 알 수 없는 것이 문제 입니다. 결국, 모든 경우의 수를 따져보고 그 가운데 최적의 해를 찾는 겁니다. 그 경우의 수를 모두 헤아리는 것은 바로 backtracking 입니다 일종의 트리를 그려나가는 것이죠. 여기서 핵심은 아이템의 수가 증가함에 따라 트리는 기하급수적으로 커진다는 겁니다. 비교대상이 지수형태로 증가하는 것 그런 문제가 NP 문제 입니다. branch and bound 는 backtracking 을 기반으로 하여 트리의 전체를 검사하지 말고 일부는 좀 가려내서 조금 시간을 단축시키자는 것입니다. 하지만 대부분의 경우 여전히 time complexity 는 2^n 변함없이 시간이 오래 걸린다는 겁니다. 어쨋든 이문제는 알고리즘에서 backtracking 파트에 나오는 가장 전형적인 문제입니다. backtracking 이란 것이 뭔가를 아셔야 합니다 이 문제는 어떤 문제인가... 특성을 이해해야 하고 과연 어느정도로 복잡한 문제인가 ? 입력(아이템 수)이 증가함에 따라 복잡도는 어떻게 증가하는 가 ? 백트래킹을 이용하여 어떤 식으로 문제를 해결해 나갈 것인가 ? 브랜치엔바운드 방법을 쓴다면 과연 가지치기(pruning)으로 어떤 방법을 채택할 것인가 ... 등등 이런 것들을 잘 조사해 가신다면 최고 점수를 받을 것 같습니다
|
||||||||||