动态规划三要素: 边界, 最优子问题, 状态转移方程;
问题描述: 现有 10 个矿工, 5 个金矿, 每个金矿有对应金子和需要开采的人数, 问你最多能够获得多少金子?
这是一个典型的动态规划问题, 动态规划的核心是如何将问题转换为重叠的子问题, 并且写出状态转移方程.
首先我们定义相应的参数:
矿工个数: n=10
金矿个数: w=5
金子数量: g=[400,500,200,300,350]
需要人数: p=[5,5,3,4,4]
p[i]代表挖了第 i 个金矿所需人数, g[i]代表挖了第 i 个金矿得到的金子数. 令 F(n,w)表示 n 个人挖 w 个金矿能够得到的最大金子数.
当 n<p[i]时, 也就是说挖第 i 个金矿的人数不够, 那么此时可以获得的最大金子数就是挖第 i-1 个金矿时的金子:
F(n,w)=F(n,w-1)
那么我们当 n>p[i]时, 有以下方程:
F(n,w)=max(F(n,w-1),F(n-p[i],w-1)+g[i])
表示 n 个人挖 w 个金矿能够得到的最大金子数 = 最大值 (n 个人挖 w-1 个金矿,((n-p[i]) 个人挖 w-1 个金矿)+g[i]))
最终代码:
- n=10
- w=5
- g=[400,500,200,300,350]
- p=[5,5,3,4,3]
- def goldMining(n,w,g,p):
- #初始化数组, 用于存储信息, 注意为了更好计算, 共有 11 列, 第一列作为辅助位
- dp = [[0 for _ in range(n+1)] for _ in range(w)]
- #边界就是 10 个人只挖第 1 个金矿
- #[0, 0, 0, 0, 0, 400, 400, 400, 400, 400, 400]
- for i in range(1,n+1):
- if i<p[0]:
- dp[0][i]=0
- else:
- dp[0][i]=g[0]
- #依次遍历金矿, 人数
- for i in range(1,w):
- for j in range(1,n+1):
- #如果当前人数小于挖这座金矿的人数
- if j<p[i]:
- #则当前最大金矿就是挖前一个金矿的相应人数的值
- dp[i][j]=dp[i-1][j]
- else:
- #否则就用如下公式计算
- dp[i][j]=max(dp[i-1][j],dp[i-1][j-p[i]]+g[i])
- return dp
- dp=goldMining(n,w,g,p)
- for i in range(len(dp)):
- print(dp[i])
最终结果:
可以看到, 我们最终可以获得的最大金子数是 900, 也就是挖第一个和第二个金矿.
来源: https://www.cnblogs.com/xiximayou/p/11964509.html