迷宮另解

 d = [

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],

[1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1],

[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],

[1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],

[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],

[1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],

[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],

[1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1],

[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],

[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],

[1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1],

[1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1],

[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

[1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1],

[1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

]

for k in range(2,30):

    for i in range(1,15):

        for j in range(1,10):

            if d[14][9]!=0:break

            if d[i][j]==k:

                if d[i+1][j]==0:d[i+1][j]=d[i][j]+1

                if d[i-1][j]==0:d[i-1][j]=d[i][j]+1

                if d[i][j+1]==0:d[i][j+1]=d[i][j]+1

                if d[i][j-1]==0:d[i][j-1]=d[i][j]+1

r = []

i,j=14,9

r.append([d[i][j],[i,j]])

while d[i][j]!=2:

    if d[i+1][j]==d[i][j]-1:

        i+=1

    elif d[i-1][j]==d[i][j]-1:

        i-=1

    elif d[i][j+1]==d[i][j]-1:

        j+=1

    elif d[i][j-1]==d[i][j]-1:

        j-=1

    r.append([d[i][j],[i,j]])    

for i in r:

    if i==r[-1]:

        print(i[1])

    else:

        print(i[1],end='->')

knapsack

 n = 7

w = 15

cost = [10, 20, 30, 40, 50,80,60]

weight = [1, 2, 3, 8, 7,1,3]

c = [0]*(w+1)

for i in range(n):

    for j in range(w,weight[i]-1,-1):

        c[j]=max(c[j],c[j-weight[i]]+cost[i])

print(max(c))

#執行結果
#230