最近在复习动态规划问题,在处理挖金矿问题的时候发现网上以python实现的代码不多,因而本身整理一份。java
问题描述:漫画图解python
公式和讲解都在上面连接的网页里面,有一点须要说明他的图片结果是错的:数组
我本身手写了一份:code
代码不知道对错,没有用java去写,直接上代码,注释写的自认为比较全,不会的好好理解下。blog
import copy def good(n,w,g=[],p=[]): # n为金矿数,w为人数,g为金矿数组,p为人数数组 arr = [0]*w for i in range(w): if (i+1)>=p[0]: # i为坐标, i+1为人数 arr[i] = g[0] res = copy.deepcopy(arr) #深copy print(res) # 上面为只有一个金矿的状况 for i in range(1,n): # 金矿数 for j in range(w): # 人工数 if (j+1)<p[i]: # j为坐标, j+1为人数 arr[j] = res[j] #和上一次状况相同 else: t = 0 if (j-p[i])<0 else j-p[i] #防止负数取到后面的值 arr[j] = max(res[j],res[t]+g[i]) #挖和不挖第i座金矿比较取大 #res[t]+g[i] 为 挖第i座金矿的状况,res[已有人数 - 第i座所需人数]+第i座金子g[i] res = copy.deepcopy(arr) print(res) return res.pop() if __name__ == '__main__': res = good(5,10,[400,500,200,300,350],[5,5,3,4,3]) print(res)
用到了深copy,不理解的去Baidu查一下,python里有拷贝,浅拷贝和深拷贝。图片
另外,有什么错误的地方欢迎你们指出。get