[数据结构][Python][经典题目][动态规划][经典01背包]求解金矿问题

一时失言乱红尘 2023-10-09 09:46 63阅读 0赞

## 题目： ##

有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。  
每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

## 思路： ##

1、首先，对于问题中的金矿，每一个金矿都存在这挖和不挖的选择  
假设：最后一个金矿不被挖掘，那么问题简化为10个人在前4个金矿中做出最优选择：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5_size_16_color_FFFFFF_t_70]  
相应的，假设最后一个金矿一定会被挖掘，问题转换成以下：由于最一个金矿消耗了3个工人，问题转换成7个工人在前4个金矿中做出最优选择。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5_size_16_color_FFFFFF_t_70 1]  
这两种简化情况，被称为全局问题的两个最优子结构。

## 动态规划要点 ##

确定全局最优解和最优子结构之间的关系，以及问题的边界，即状态转移方程。  
以上，可以吧金矿数量设为n，工人数量设置为w，金矿的含金量设为数组g\[\]，金矿所需开采人数设为数组p\[\]，设F(n,w)为n个金矿，w个工人时的最优收益函数，那么状态转移方程为F(n,w)(n=0或w=0)  
问题的边界为金矿数量为0或者工人数量为0的情况。  
F(n,w)=F(n-1,w)(n>=1,w<p\[n-1\])  
所剩的工人不够挖掘当时的金矿时，只有一种最优子结构。  
F(n,w)=Max(F(n-1,w),F(n-1,w-p\[n-1\])+g\[n-1\])(n>=1,w>=p\[n-1\])  
在常规的情况下，具有两种最优子结构（挖当前的金矿或者不挖当前的金矿）。

## 求解过程 ##

![在这里插入图片描述][20190928155516425.png]  
表格最左侧代表不同的金矿选择范围，从上到下，每多增加行，就代表多1个金矿可供选择，也就是F(n,w)函数中的n值  
表格的最上方代表工人的数量，从1个工人到10个工人，也就是F(n,w)函数的w值  
下面我们从第1行第1列开始，尝试把空白的格子一一填满，填充的依据是状态转移方程。  
对于第一行的前四格子，由于w<p\[n-1\]，对应的状态转移方程为:  
F(n,w)=F(n-1,w)(n>1,w<p\[n-1\])  
带入求解：  
F(1,1)=F(1-1,1)=F(0,1)=0  
F(1,2)=F(1-1,2)=F(0,2)=0  
F(1,3)=F(1-1,3)=F(0,3)=0  
F(1,4)=F(1-1,4)=F(0,4)=0  
![在这里插入图片描述][20190928161512350.png]  
第1行的后6个格子：此时w>=p\[n-1\]，对于如下公式：  
F(n,w)=Max(F(n-1,w),F(n,w-p\[n-1\])+g\[n-1\])(n>1,w>=p\[n-1\])  
带入求解：  
F(1,5)=Max(F(1-1,5),F(1-1,5-5)+400)=Max(F(0,5),400))=400  
…  
F(1,10)=Max(F(1-1,10),F(1-1,10-5)+400)=Max(F(0,5),400))=400  
![在这里插入图片描述][20190928162111329.png]  
…  
![在这里插入图片描述][20190928162619440.png]

## 优化 ##

4个金矿、9个工人的最优结果，是由他的两个最优子结构，也就是3个金矿、5个金矿和3个金矿、9个工人的结果推导出来。这两个最优子结构都位于他的上一行。  
所以，在程序中并不需要保持整个表格，无论金矿有多少座，我们只要保存1行的数据即可。在计算下一行的时候，要从右向左统计，把旧数据一个一个替换掉。

## 代码 ##

def getGoldMing(w,p,g):
        result = [0 for x in range(w+1)]
        for i in range(1,len(g)+1):
            for j in range(w,-1,-1):
                if j>=p[i-1]:
                    result[j]=max(result[j],result[j-p[i-1]]+ g[i-1])
    
        return result[w]
    
    if __name__ == '__main__':
        w = 10
        p = [5, 5, 3, 4, 3]
        g = [400, 500, 200, 300, 350]
        res = getGoldMing(w,p,g)
        print(res)

![在这里插入图片描述][2019092700225461.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190925000527396.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190925000717645.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5,size_16,color_FFFFFF,t_70
[20190928155516425.png]: https://img-blog.csdnimg.cn/20190928155516425.png
[20190928161512350.png]: https://img-blog.csdnimg.cn/20190928161512350.png
[20190928162111329.png]: https://img-blog.csdnimg.cn/20190928162111329.png
[20190928162619440.png]: https://img-blog.csdnimg.cn/20190928162619440.png
[2019092700225461.png]: https://img-blog.csdnimg.cn/2019092700225461.png