动态规划挖金矿问题——python实现

　

挖金矿

最近在复习动态规划问题，在处理挖金矿问题的时候发现网上以Python实现的代码很少，于是自己整理一份。

问题描述：漫画图解

公式和讲解都在上面链接的网页里面，有一点需要说明他的图片结果是错的：

我自己手写了一份：

代码不知道对错，没有用java去写，直接上代码，注释写的自认为比较全，不会的好好理解下。

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里有拷贝，浅拷贝和深拷贝。

另外，有什么错误的地方欢迎大家指出。

相关阅读

一个高效的seo工作者有些问题一定要重视

　　电子商务，网络办公，已经变成新时代企事业单位回避不了的问题，新网站上线如何迅速获得流量并且变现，也成了seo工作者绞尽脑汁要搞

网站建设要考虑的问题

网站建设要考虑的问题。在互联网的时代中，网站建设其实是一个非常常见的事情了，几乎每一家企业都希望在互联网上，能够留下属于自己一

如何处理网站兼容性问题

　　当前网络发展迅速的新时代，有许多网站建设公司，因为浏览器的兼容性问题，网站的管理员付出了很多的努力去完善，除了浏览器之外，还

关于layuiAdmin 后台管理模板购买授权的问题

购买授权之前，建议认真阅读下述 “解惑”，以免造成不必要的困惑。另外也可以阅读 《layui 付费产品服务条款》注意：layuiAdmin 受国

解决FTP上传文件速度慢的问题

 我们在利用ftp的storeFile（）上传存储文件的时候，为了让上传速度提升，建议采用添加缓冲区的方式，根据上传文件的大       小，设置