用记忆法解决水壶问题-yiteyi-C++库

给两个最大容量为 M 和 N 升。水罐上没有可以帮助我们测量较小数量的标记。任务是测量 D 使用这两个水罐的水升。因此，我们的目标是从初始状态（m，n）达到最终状态（0，d）或（d，0）。

null

例如：

输入： 4 3 2 输出： (0, 0) –> (4, 0) –> (4, 3) –> (0, 3) –> (3, 0) –> (3, 3) –> (4, 2) –> (0, 2)

输入： 5 2 4 输出： (0, 0) –> (5, 0) –> (5, 2) –> (0, 2) –> (2, 0) –> (2, 2) –> (4, 0)

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法： 使用 BFS 已在上一节中讨论过邮递 .在这篇文章中，使用回忆录和递归已经讨论过了。在任何情况下，共有六种可能性：

把第一个罐子完全倒空
把第二个罐子完全倒空
装满第一个罐子
把第二个罐子装满
将第二个水罐中的水注入第一个水罐，直到第一个水罐装满水或第二个水罐没有水为止
将第一个水罐中的水注入第二个水罐，直到第二个水罐装满水或第一个水罐没有水为止

方法：使用递归，逐一访问所有六个可能的动作，直到其中一个返回为真。由于可以重复相同的递归调用，因此每个返回值都使用回忆录避免再次调用递归函数并返回存储值。

以下是上述方法的实施情况：

                     # This function is used to initialize the                   
                     # dictionary elements with a default value.                   
                     from                               collections                               import                               defaultdict                   
                             
                     # jug1 and jug2 contain the value                   
                     # for max capacity in respective jugs                   
                     # and aim is the amount of water to be measured.                   
                     jug1, jug2, aim                               =                               4                               ,                               3                               ,                               2                   
                             
                     # Initialize dictionary with                   
                     # default value as false.                   
                     visited                               =                               defaultdict(                               lambda                               :                               False                               )                   
                             
                     # Recursive function which prints the                   
                     # intermediate steps to reach the final                   
                     # solution and return boolean value                   
                     # (True if solution is possible, otherwise False).                   
                     # amt1 and amt2 are the amount of water present                   
                     # in both jugs at a certain point of time.                   
                     def                               waterJugSolver(amt1, amt2):                   
                             
                                         # Checks for our goal and                   
                                         # returns true if achieved.                   
                                         if                               (amt1                               =                               =                               aim                               and                               amt2                               =                               =                               0                               )                               or                               (amt2                               =                               =                               aim                               and                               amt1                               =                               =                               0                               ):                   
                                         print                               (amt1, amt2)                   
                                         return                               True                   
                             
                                         # Checks if we have already visited the                   
                                         # combination or not. If not, then it proceeds further.                   
                                         if                               visited[(amt1, amt2)]                               =                               =                               False                               :                   
                                         print                               (amt1, amt2)                   
                             
                                         # Changes the boolean value of                   
                                         # the combination as it is visited.                   
                                         visited[(amt1, amt2)]                               =                               True                   
                             
                                         # Check for all the 6 possibilities and                   
                                         # see if a solution is found in any one of them.                   
                                         return                               (waterJugSolver(                               0                               , amt2)                               or                   
                                         waterJugSolver(amt1,                               0                               )                               or                   
                                         waterJugSolver(jug1, amt2)                               or                   
                                         waterJugSolver(amt1, jug2)                               or                   
                                         waterJugSolver(amt1                               +                               min                               (amt2, (jug1                               -                               amt1)),                   
                                         amt2                               -                               min                               (amt2, (jug1                               -                               amt1)))                               or                   
                                         waterJugSolver(amt1                               -                               min                               (amt1, (jug2                               -                               amt2)),                   
                                         amt2                               +                               min                               (amt1, (jug2                               -                               amt2))))                   
                             
                                         # Return False if the combination is                   
                                         # already visited to avoid repetition otherwise                   
                                         # recursion will enter an infinite loop.                   
                                         else                               :                   
                                         return                               False                   
                             
                     print                               (                               "Steps: "                               )                   
                             
                     # Call the function and pass the                   
                     # initial amount of water present in both jugs.                   
                     waterJugSolver(                               0                               ,                               0                               )                   

输出：

时间复杂性 ：O（M*N） 辅助空间 ：O（M*N）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章