| [ QuizWit ] in KIDS 글 쓴 이(By): outsider (하얀까마귀) 날 짜 (Date): 2001년 12월 12일 수요일 오전 02시 50분 22초 제 목(Title): 게임하다가... 어떤 게임을 하다가 머리쓰기가 싫증이 나서 옵티멀한 전략을 찾아서 자동 화해보려고, 게임 진행을 좀 추상화시킨 뒤에 알고리즘을 궁리해봤습니다. 정리해놓고 보니까 규칙은 굉장히 일반적인 모양으로 보이는데 최적 혹은 대충 근사한 알고리즘이 안 나오는군요. 풀어주시거나 뭘 참고해야 할 지 힌트 부탁드립니다. :) - 도시들이 있고, 도시들을 연결하는 길들이 있는 graph이다. - 몇 가지 종류의 상품들이 있는데, 각 도시들은 각각의 상품을 몇 개인가 갖고 있거나, 또는 최대 몇 개까지 구입하려고 한다. (몇개의 상품을 갖고 있으면서, 더 많은 수의 상품을 구입하려고 하는 경우도 있다.) 상품들의 구입가격 혹은 판매가격은 도시마다 다르다. - 상품은 길을 통해 운반되는데 길의 bandwidth가 한정되어 있다. - 도시 A와 B 사이의 길의 bandwidth가 10이라면, 이 길을 따라서 A->B로 최대 10개, B->A로 최대 10개의 상품이 동시에 운반될 수 있다. - 길이 허용하는 한 상품은 여러개의 도시를 지나 얼마의 거리든지 이동할 수 있다. * 도시,길,상품이 주어졌을 때 상품들을 운반해 최대수익을 올리는 해를 구 하려면? * 길의 bandwidth를 확장할 기회가 생겼을 때 어떤 길을 확장해야 수익이 제일 많이 증가하는 지 알려면? (지금 도마 위에 올린 게임의 경우 도시는 50개 정도, 도시는 보통 1-3개 정도의 다른 도시와 연결될 수 있습니다. 웬만한 시간 복잡도는 용서가 될 것 같은 느낌이...^^) ps. 참고로 해당 게임은 마키아밸리 더 프린스입니다. --a -- @< //) `//<_ 하얀까마귀 |