N个人过河，船每次只能坐两个人，船载每个人过河的所需时间不同七口，每次过江 间为船上的人的较慢的那个，求最快的过河时间。（船划过去要有一个人划回来。 假设有7个人要过河，每个人的过河所需要要的时间分別是1,3,4,5,8,2,9 设计算法并编程求解。

这是一个经典的搜索问题，可以使用回溯法来解决。

具体来说，我们可以采用深度优先搜索的方式来搜索所有可能的方案。对于每个状态，我们考虑所有可能的选择，即选择哪两个人过河，然后根据问题的限制条件来判断这个选择是否合法。如果选择是合法的，我们就继续搜索下一个状态，否则就回溯到上一个状态。在搜索的过程中，我们需要维护当前已过河和未过河的人的集合，以及已经花费的时间。

具体的实现细节可以参考下面的代码实现：

def cross_river(people):
    n = len(people)
    time = [0]  # 记录花费的总时间

    def dfs(used, left, right):
        # 判断是否已经过完
        if not left:
            time[0] = min(time[0], used)  # 更新最小花费时间
            return

        # 每次选择两个人过河
        for i in range(len(left)):
            for j in range(i + 1, len(left)):
                new_left = left[:i] + left[i + 1:j] + left[j + 1:]  # 更新未过河的人的集合
                new_right = right + [left[i], left[j]]  # 更新已过河的人的集合
                new_used = used + max(people[i], people[j])  # 更新花费的时间

                # 判断这个选择是否合法
                if time[0] == 0 or new_used < time[0]:  # 剪枝1：如果当前花费时间已经超过了最小花费时间，就不用尝试了
                    dfs(new_used, new_left, new_right)

    dfs(0, people, [])
    return time[0]

使用上述代码，我们可以得到7个人过河的最短时间为 29，即第一个人和第二个人一起过河，花费时间为 3，然后第二个人划船回来，花费时间为 3，接着第五个人和第七个人一起过河，花费时间为 9，然后第一个人划船回来，花费时间为 1，接着第一、二、三个人一起过河，花费时间为 4，最后第二个人划船回来，花费时间为 3。