algorithm - 可能的 "boat loads"

Question

你知道 river-crossing problems .这是排序说明:

Once upon a time, three cannibals were guiding three missionaries through a jungle. They were on their way to the nearest mission station. After some time, they arrived at a wide river, filled with deadly snakes and fish. There was no way to cross the river without a boat. Fortunately, they found a row boat with two oars after a short search. Unfortunately, the boat was too small to carry all of them. It could barely carry two people at a time. Worse, because of the river's width there was no way to bring the boat back other than to row it back. Since the missionaries could not trust the cannibals they had to figure out a plan to get all six of them safely across the river. The problem was that these cannibals would kill and eat missionaries as soon as there were more cannibals than missionaries at some place. Thus our missionary-programmer had to devise a plan that guaranteed that there were never any missionaries in the minority at either side of the river. The cannibals, however, can be trusted to cooperate otherwise. Specifically, they won't abandon any potential food, just as the missionaries won't abandon any potential converts.

我的问题是这个问题的一部分。我正在尝试设计一个返回可能船载列表的函数(例如，如果 boat_capacity 为 3，则 [(3mis, 0can), (2mis, 1can), (1mis, 1can), ...] )。我有 num(传教士或食人者的数量)和 boat-capacity 作为我函数的输入。

您如何设计函数和算法？

Answer 1

以递归的方式考虑这个问题，也就是说您想根据可能的子问题来考虑它。所以，如果你有一艘满载三名乘客的船，那显然就像一艘只有一名乘客的船，加上两名乘客的任意组合。

有两名乘员的船有一名乘员加上“满载一人的船”。

所以你的算法基本上看起来像

to find all combinations of n occupants,
    pick an occupant
    if n = 1 return
    if n > 1 find all combinations of (n-1) occupants.

请注意，这不是精确解决方案，因为这看起来很像家庭作业问题。