问题：大盗潜入博物馆，面前有5件宝物，分别有重量和价值，大盗的背包仅能负重20公斤，请问如何选择宝物得到的总价值最高？
博物馆大盗问题
我们把这个问题记为m(i,W)函数，其中i为宝物，W为重量，v为价值：前i(1<=i<=5)个宝物中，组合不超过W(1<=i<=20)重量，得到最大价值
m(i,W)应该是m(i-1,W)和m(i-1,W-Wi)+vi两者中的最大值，前者放不下最大宝物，后者能放。
公式
我们从m(1，1)开始计算到m(5，20)。可以画一个表格，如下：
动态规划表
由公式可知m(5，5)=m(4，5)=max( m(3，5)，m(3，0)+8）
通过公式，我们可以把代码写出来，如下：
动态规划算法代码
当然我们也可以用递归的方法（通过备忘录）来解决博物馆大盗问题，就不要推导公式，代码也更简洁直观。代码如下：
递归代码
问题：大盗潜入博物馆，面前有5件宝物，分别有重量和价值，大盗的背包仅能负重20公斤，请问如何选择宝物得到的总价...
解决打包过大的问题 用 Pyinstaller 打包 Python 程序 + 解决打包结果过大 >>[https:...
动态规划算法 动态规划算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。其基本思想也...
动态规划算法介绍 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决...
Mac Vim Python 调用问题解决方法 vim link python 2 最好的方法用macvim取...
一、概念 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。...
动态规划 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。...
Java使用动态规划算法思想解决背包问题 背包问题是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种...
[Python Subprocess Popen 管道阻塞问题分析解决] 使用subprocess库时可以用wai...
本文会介绍怎么用python解决线性规划问题，为什么要用python而不是matlab和lingo呢？因为matl...
本文标题：python：用动态规划算法来解决博物馆大盗问题
本文链接：https://www.haomeiwen.com/subject/qsudphtx.html
网友评论