동길이와 친구 5명, 총 6명의 일행이 자연 체험 여행을 떠났다. 어떤 지역에 이르러 강을 건너야 할 상황이 되었는데, 그 곳에는 보트가 한 척 있으며, 그 보트에는 최대 두 명이 탈 수 있다. 6명이 모두 강을 건너기 위해선 우측 그림에서 보듯이 강 이편과 저편 사이로 보트를 여러 번 왔다갔다 해야 한다.
이들이 모두 강을 건넌 후, 보트는 강 반대편에 두어도 된다.
보트 사용료는 특이하게도 보트를 사용하는 사람의 몸무게에 비례하여 지불해야 한다. 단, 두 사람이 탈 경우 몸무게가 무거운 사람의 비용을 지불하면 다른 사람은 공짜로 탈 수 있다.
6명 몸무게가 각각 (9,12,7,8,15,3)라고 할 때, 최소 비용으로 모두 강을 건널 경우 그 비용은 얼마인가?