python递归解决博物馆大盗问题

本文主要是介绍python递归解决博物馆大盗问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

兄弟萌，话不多说，show me the code!

# 初始化记忆表格m
# key是(宝物组合,最大重量),value是最大价值
m = {}def thief(tr,w):if tr==set() or w==0: # turple是key的要求m[(tuple(tr),w),w] = 0return 0elif (tuple(tr),w) in m:return m[(tuple(tr),w)]else:vmax = 0for t in tr:if t[0] <= w:# 逐个从集合中去掉某个宝物,递归调用# 选出所有价值中的最大值v = thief(tr-{t},w-t[0])+t[1]vmax = max(vmax,v)m[(tuple(tr),w)] = vmaxreturn vmaxif __name__ == '__main__':tr = {(2, 3), (3, 4), (4, 8), (5, 8), (9, 10)}# 大盗最大承重maxW = 20print(thief(tr,maxW))

 

这篇关于python递归解决博物馆大盗问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---