不懂吃鱼k
2021-06-12 22:51
采纳率: 83.3%
浏览 23

python动态规划多边形游戏求一个回溯求删除边顺序的代码

这是我用python写的多边形游戏的代码,但是只能输出第一次删除的边的下标和最终的最大值,希望大佬能帮我补充一段回溯求每次删除边的顺序的代码,感谢,我实在写不出,总是报错

我代码中max_l[i][j]表示的是长度(包含节点数)为i,起始点下标为j的链的最大值

另外,我这个算法中输入的顺序是先边后点

例如+,-7,+,4,*,2,*,5

import numpy as np
def function(n,i,j):#n为节点数,i为包含节点个数,j为开始节点
    for k in range(1,i):
        break_point=j+k#k为左子链长度
        if break_point>n:
            break_point=break_point%n#确定断点位置
        a=min_l[k][j]
        b=max_l[k][j]
        c=min_l[i-k][break_point]
        d=max_l[i-k][break_point]
        if side_value[break_point]=='+':#如果两线段之间的符号为‘+’,最大最小值的情况
            maximum=b+d
            minimum=a+c
        else:#如果两线段之间的符号为‘*’,最大最小值的情况
            maximum=max(a*c,a*d,b*c,b*d)
            minimum=min(a*c,a*d,b*c,b*d)
        min_l[i][j]=min(minimum,min_l[i][j])
        max_l[i][j]=max(maximum,max_l[i][j])
def find_max(m):
    maximum=0
    for i in range(1,len(m)):
        if m[i]>maximum:
            maximum=m[i]
            flag=i
    return [maximum,flag]
n=int(input('请输入节点个数'))
print('请输入各个节点的值和边的符号:\n')
point_value=[0 for i in range(n+1)]
side_value=[0 for i in range(n+1)]
for i in range(1,n+1):
    side_value[i]=str(input('请输入第'+str(i)+'条边的符号(+/*)\n'))
    point_value[i]=int(input('请输入第'+str(i)+'个节点的值\n'))
max_l=np.array([[-1024 for i in range(n+1)]for j in range(n+1)])
min_l=np.array([[1024 for i in range(n+1)]for j in range(n+1)])
min_l[1]=point_value#包含节点数为1时,线段的最大最小值都为本身
max_l[1]=point_value
for i in range(2,n+1):
    for j in range(1,n+1):
        function(n,i,j)
print('最小值矩阵为:')
print(min_l[1:n+1,1:n+1])
print('最大值矩阵为:')
print(max_l[1:n+1,1:n+1])
max_final=find_max(max_l[n])[0]
flag=find_max(max_l[n])[1]
for i in range(1,len(max_l[n])):
    print('删除第'+str(i)+'条边时最大值为'+str(max_l[n][i]))
print('删除第'+str(flag)+'条节点时值最大,最大值为',max_final)

下面是我现在的输出

 

  • 点赞
  • 收藏

1条回答 默认 最新

  • 有问必答小助手 2021-06-16 17:22
    已采纳

    你好,我是有问必答小助手,非常抱歉,本次您提出的有问必答问题,技术专家团超时未为您做出解答

    本次提问扣除的有问必答次数,已经为您补发到账户,我们后续会持续优化,扩大我们的服务范围,为您带来更好地服务。

    点赞 打赏 评论

相关推荐 更多相似问题