3个壶 - 解决方案的概念化问题

Question

所以水壶问题很有名。使用容量为a和b的两个罐子，得到体积d。这些罐子没有标记

所以我想试着解决3罐容量的a，b和c

下面的代码显示了一个单一问题的解决方案，其中罐子是大小的： 5、3和1，目标卷是4。我已经列出了所有可能的组合，以便该计划作为可能的资产进行工作，只是因为这样可以更容易地解释我的问题

所以我的代码基本上就是把最大的罐子倒进第二大的罐子，如果有空间等等（对于较小的罐子，它首先向上工作，例如：如果5是空的，3是满的，3会变成5）。很明显，尽管（如：（5，0，0）的解决方案所示），这并不总是最好的方法。对于（5,0,0），最好的方法实际上是将5清空为1。这需要两个步骤才能得到4:（5,0,0）和（4,0,1）

（5,3,0）得出正确答案的唯一原因是5不能倒进2号罐，所以尽可能多地倒进1号罐

我的问题是，如何编写三罐问题的代码，以确保我可以在进一步的步骤（4,0,1）中找到解决方案（5,0,0），而不是迭代（2,3,0）

事实是，我实际上对为任意数量的罐子编写解决方案很感兴趣，但无法从概念上解决如何做到这一点

请注意，我是一个初学者程序员，不太了解循环以外的函数

global memory
global listSolution

capacity = (5,3,1)
#Set jug capacity 
jug1Max = capacity[0]
jug2Max = capacity[1]
jug3Max = capacity[2]

def statusJugs(state):
  #set jug status 
  jug1 = state[0]
  jug2 = state[1]
  jug3 = state[2]

  if(jug1==4 or jug2==4 or jug3 ==4):
      listSolution.append(state)
      return True

  #Has jug state been visited 
  if((jug1,jug2,jug3) in memory):
      return False

  memory[(jug1,jug2,jug3)] = 1

  #empty jug1
  if(jug1>0):
      #empty jug1 into jug2
      if(jug1+jug2<=jug2Max):
          if(statusJugs((0,jug1+jug2,jug3))):
              listSolution.append(state)
              return True
      else:
          if(statusJugs((jug1-(jug2Max-jug2), jug2Max, jug3)) ):
              listSolution.append(state)
              return True
      #empty jug1 into jug3
      if(jug1+jug3<=jug3Max):
          if( statusJugs((0,jug2,jug1+jug3))):
              listSolution.append(state)
              return True
      else:
          if( statusJugs((jug1-(jug3Max-jug3), jug2, jug3Max)) ):
              listSolution.append(state)
              return True

  #empty jug2
  if(jug2>0):
      #empty jug2 into jug1
      if(jug1+jug2<=jug1Max):
          if( statusJugs((jug1+jug2, 0, jug3)) ):
              listSolution.append(state)
              return True
      else:
          if( statusJugs((jug1Max, jug2-(jug1Max-jug1), jug3)) ):
              listSolution.append(state)
              return True
      #empty jug2 into jug3
      if(jug2+jug3<=jug3Max):
          if( statusJugs((jug1, 0, jug2+jug3)) ):
              listSolution.append(state)
              return True
      else:
          if( statusJugs((jug1, jug2-(jug3Max-jug3), jug3Max)) ):
              listSolution.append(state)
              return True

  #empty jug3
  if(jug3>0):
      #empty jug3 into jug1
      if(jug1+jug3<=jug1Max):
          if( statusJugs((jug1+jug3, jug2, 0)) ):
              listSolution.append(state)
              return True
      else:
          if( statusJugs((jug1Max, jug2, jug3-(jug1Max-jug1))) ):
              listSolution.append(state)
              return True
      #empty jug3 into jug2
      if(jug2+jug3<=jug2Max):
          if( statusJugs((jug1, jug2+jug3, 0)) ):
              listSolution.append(state)
              return True
      else:
          if( statusJugs((jug1, jug2Max, jug3-(jug2Max-jug2))) ):
              listSolution.append(state)
              return True

  return False

possibleStates = [(5,3,1),(5,3,0),(5,0,1),(5,0,0),(0,3,1),(0,3,0),(0,0,1)]
for counter in range (0,len(possibleStates)):
    listSolution = []
    memory={}
    initial_state = possibleStates[counter]
    print("Solution for:",possibleStates[counter])
    statusJugs(initial_state)
    listSolution.reverse()
    print (listSolution)
    print ("Length of solution is:", len(listSolution))
    print ("\n=======End of solution=======")

Answer 1

在面向对象编程中，这将是一个非常好的练习。我建议您花一些时间来学习（使用Python）。如果做得好，您将得到更简单、更易于检查和理解的代码。祝你好运