0

我目前正在研究水壶问题，并且几乎完成了。我的要求第一个 (a) 瓶子有 8 升水，但另外两个 (b 和 c) 是空的。我可以让它让我的第一个被填满，但不能完成其他两个空的其他条件。如果我给一个 and 运算符（a == 8 和 b == 0 和 c == 0），程序不会运行。注意：DFS 正在用于此。

这是我的程序：

capacity = (10,6,5) 
# Maximum capacities of 3 jugs -> x,y,z
x = capacity[0]
y = capacity[1]
z = capacity[2]

# to mark visited states
memory = {}

# store solution path
ans = []

def get_all_states(state):
    # Let the 3 jugs be called a,b,c
    a = state[0]
    b = state[1]
    c = state[2]

    if(a==8 and b==0 and c==0):
        ans.append(state)
        return True

    # if current state is already visited earlier
    if((a,b,c) in memory):
        return False

    memory[(a,b,c)] = 1

    #empty jug a
    if(a>0):
        #empty a into b
        if(a+b<=y):
            if( get_all_states((0,a+b,c)) ):
                ans.append(state)
                return True
        else:
            if( get_all_states((a-(y-b), y, c)) ):
                ans.append(state)
                return True
        #empty a into c
        if(a+c<=z):
            if( get_all_states((0,b,a+c)) ):
                ans.append(state)
                return True
        else:
            if( get_all_states((a-(z-c), b, z)) ):
                ans.append(state)
                return True

    #empty jug b
    if(b>0):
        #empty b into a
        if(a+b<=x):
            if( get_all_states((a+b, 0, c)) ):
                ans.append(state)
                return True
        else:
            if( get_all_states((x, b-(x-a), c)) ):
                ans.append(state)
                return True
        #empty b into c
        if(b+c<=z):
            if( get_all_states((a, 0, b+c)) ):
                ans.append(state)
                return True
        else:
            if( get_all_states((a, b-(z-c), z)) ):
                ans.append(state)
                return True

    #empty jug c
    if(c>0):
        #empty c into a
        if(a+c<=x):
            if( get_all_states((a+c, b, 0)) ):
                ans.append(state)
                return True
        else:
            if( get_all_states((x, b, c-(x-a))) ):
                ans.append(state)
                return True
        #empty c into b
        if(b+c<=y):
            if( get_all_states((a, b+c, 0)) ):
                ans.append(state)
                return True
        else:
            if( get_all_states((a, y, c-(y-b))) ):
                ans.append(state)
                return True

    return False

initial_state = (10,0,0)
print("Starting work...\n")
get_all_states(initial_state)
ans.reverse()
for i in ans:
    print(i)
4

0 回答 0